Input
输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值
Output
输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。
Sample Input
3
1 2
3 2
4 5
1 2
3 2
4 5
Sample Output
2
1、洛谷P1147 连续自然数和 [2017年6月计划 数论01]
2、Java文件类型工具类
3、linq
4、JavaScript三种弹出框(alert,confirm和prompt)用法举例
5、WEB引入Google思源黑体
HINT
【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000
Source
思路:
这题的并查集做法简直逆天;
通过并查集把可能重复的属性都给链接到一块;
然后就开始进行合并判断哪些属性能用到;
然后从1开始到10000遍历;
哪个属性是false(没被合并)最大就是到那;
来,上代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define maxn 100005 using namespace std; int n,f[maxn]; bool if_[maxn]; char Cget; inline void in(int &now) { now=0,Cget=getchar(); while(Cget>'9'||Cget<'0') Cget=getchar(); while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } return ; } int find(int x) { if(x==f[x]) return x; f[x]=find(f[x]); return f[x]; } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); in(n);int x,y; for(int i=1;i<=10000;i++) f[i]=i; for(int i=1;i<=n;i++) { in(x),in(y); x=find(x),y=find(y); if(x==y) if_[x]=true; else { if(x>y) swap(x,y); f[x]=y; if_[x]=true; } } for(int i=1;i<=10001;i++) { if(!if_[i]) { printf("%d\n",i-1); break; } } return 0; fclose(stdin); fclose(stdout); }优质内容筛选与推荐>>
1、洛谷P1147 连续自然数和 [2017年6月计划 数论01]
2、Java文件类型工具类
3、linq
4、JavaScript三种弹出框(alert,confirm和prompt)用法举例
5、WEB引入Google思源黑体