题解 | #[SCOI2010]游戏#

题意：你有n件装备，每件装备有两个属性，每件装备只能用一次，你打boss时属性只能从1开始连续用装备攻击，求你的最大攻击次数。
思路：不会什么二分图匹配，也想不到并查集，只能硬贪了。
贪心的思路是：让所有的边都做出尽可能多的贡献。用 pair 存入所有的x,y，并以左端点为第一关键字，右端点为第二关键字进行排序。最后进行装桶：先使当前编号的x对应的桶++，如果那个桶已经被装过了，那么这个编号的x对答案没有任何贡献了，就转而将这个编号的y对应的那个结点++。(什么你问如果也被装入了怎么办？那说明这个编号一点用都没有了，对答案无影响。
处理完后对桶数组进行线性扫描即可，遇到空桶就退出，答案为i-1。注意如果所有桶都装了，那么答案会是n-1,所以需要对循环上限+1，否则会wa.
下面给出代码。

#include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
const int maxn=1000005;
int vis[maxn];
int n,maxx,ans;
P p[maxn];
bool cmp(P a,P b){
    if(a.first!=b.first)    return a.first<b.first;
    return a.second<b.second;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        maxx=max(maxx,y);
        p[i].first=x,p[i].second=y;
    }
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(!vis[p[i].first])    vis[p[i].first]=1;
        else                    vis[p[i].second]=1;
    }
    for(int i=1;i<=maxx+1;i++)    if(!vis[i]) {ans=i-1;break;};
    cout<<ans;
}