题意:你有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; }