桑沫严
(桑沫严)
1
二分答案+贪心
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,a[N],b[N];
bool check(int x){
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i]>=cnt&&b[i]>=x-cnt-1) cnt++;
if(cnt>=x) break;
}
return cnt>=x;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
int l=1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
return 0;
}
桑沫严
(桑沫严)
2
又改了一下，但是无济于事 
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n;
pair<int,int> a[N];
bool check(int x){
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i].first>=cnt&&a[i].second>=x-cnt-1) cnt++;
if(cnt>=x) break;
}
return cnt>=x;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+n+1,[](const pair<int,int>& a,const pair<int,int>& b){
return a.first+a.second<b.first+b.second;
});
int l=1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
return 0;
}
桑沫严
(桑沫严)
4
用 cnt 表示已经选了的个数，把所有的朋友从钱少到钱多扫一遍，如果满足最多比他贫穷的人大于等于已经选了的人数，且最多比他富有的人大于等于还需要选的人数，就把他选上。（first 和 second 好像写反了，但是改过来也是 0 分）
2345安全卫士
(蛋小黄（蒟蒻）)
5
我跟你思路类似，好像就是二分底下部分不太一样【不过我AC了嘻嘻】
1 个赞
桑沫严
(桑沫严)
7
就是优先选择那些对富有人数和贫穷人数限制较宽松的朋友
桑沫严
(桑沫严)
12
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n;
pair<int,int> a[N];
bool check(int x){
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i].second>=cnt&&a[i].first>=x-cnt-1) cnt++;
if(cnt>=x) break;
}
return cnt>=x;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+n+1,[](const pair<int,int>& x,const pair<int,int>& y){
return x.first+x.second<y.first+y.second;
});
int l=1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
return 0;
}
样例过了
2345安全卫士
(蛋小黄（蒟蒻）)
13
初始代码，check部分a[i],b[i]顺序变一下就能AC
@桑沫严
2 个赞
