Description
Link
(lxhgww)最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用([1,10000])之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，(lxhgww)遇到了终极(boss)，这个终极(boss)很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对(boss)产生伤害。也就是说一开始的时候，(lxhgww)只能使用某个属性值为1的装备攻击(boss)，然后只能使用某个属性值为2的装备攻击(boss)，然后只能使用某个属性值为(3)的装备攻击(boss)……以此类推。现在(lxhgww)想知道他最多能连续攻击(boss)多少次？
不会概括
(n<=10^5)
Solution
可以贪心。
用一个(vector)记录所有的属性值对应的有哪几个下标
(q[x])表示（两个属性值中有一个为(x) ）的下标集合
从小到大枚举现在攻击到哪（枚举(x)），在(q[x])中找用哪一个。
情况一：某个装备的较大属性值为(x)
由于这个装备的较小属性值已经有别的人选过了，所以选这个装备对后续操作没有任何影响，直接选它就好了
情况二：某个装备的较小属性值为(x)
那么，我们就要选这种装备中较大属性值最多的那一个。
如果有多个最多值，就选较大属性值尽量大的，保证不浪费。
用过的点打上标记，同时数量--
还可以优化一点：
我们发现装备的较大值只需要统计数量，不需要枚举，所以就不用加到(vector)里去，要用的时候直接减就可以了。
Code
#include<bits/stdc++.h>
#define N (1000010)
using namespace std;
struct xbk{int l,r;}a[N];
int n,cnt[N];
vector<int>q[N];
bool used[N];
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
int l=read(),r=read();
if(l>r) swap(l,r);
if(r>n) r=n+2;
a[i].l=l,a[i].r=r;
q[l].push_back(i);
cnt[r]++;
}
for(int i=1;i<=n+1;i++){
int maxn=-1,now=0,maxx=0;
bool flag=0;
if(cnt[i]){
cnt[i]--;
continue;
//情况一
}
for(int j=0;j<(int)q[i].size();j++){
int id=q[i][j];
flag=1;
if(cnt[a[id].r]>maxn||(cnt[a[id].r]==maxn&&a[id].r>maxx)){
maxn=cnt[a[id].r];
maxx=a[id].r;
now=id;
}
//情况二
}
cnt[a[now].r]--;
if(!flag){
printf("%d
",i-1);
return 0;
}
}
return 0;
}