1854: [Scoi2010]游戲

Time Limit:?5 Sec??Memory Limit:?162 MB
Submit:?4938??Solved:?1948
[Submit][Status][Discuss]

Description

lxhgww最近迷上了一款游戲，在游戲里，他擁有很多的裝備，每種裝備都有2個屬性，這些屬性的值用[1,10000]之間的數表示。當他使用某種裝備時，他只能使用該裝備的某一個屬性。并且每種裝備最多只能使用一次。 游戲進行到最后，lxhgww遇到了終極boss，這個終極boss很奇怪，攻擊他的裝備所使用的屬性值必須從1開始連續遞增地攻擊，才能對boss產生傷害。也就是說一開始的時候，lxhgww只能使用某個屬性值為1的裝備攻擊boss，然后只能使用某個屬性值為2的裝備攻擊boss，然后只能使用某個屬性值為3的裝備攻擊boss……以此類推。 現在lxhgww想知道他最多能連續攻擊boss多少次？

Input

輸入的第一行是一個整數N，表示lxhgww擁有N種裝備 接下來N行，是對這N種裝備的描述，每行2個數字，表示第i種裝備的2個屬性值

Output

輸出一行，包括1個數字，表示lxhgww最多能連續攻擊的次數。

Sample Input

3
1 2
3 2
4 5

Sample Output

2

HINT

【數據范圍】
對于30%的數據，保證N < =1000
對于100%的數據，保證N < =1000000

Source

?

?

思路：

　　這題的并查集做法簡直逆天；

　　通過并查集把可能重復的屬性都給鏈接到一塊；

　　然后就開始進行合并判斷哪些屬性能用到；

　　然后從1開始到10000遍歷；

　　哪個屬性是false（沒被合并）最大就是到那；

?

?

來，上代碼：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>#define maxn 100005using 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); }

?

轉載于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6622775.html

總結

以上是生活随笔為你收集整理的AC日记——[SCOI2010]游戏 bzoj 1854的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。