D二分答案是错的吗

// Problem: 小苯的区间选数2.0
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/119895/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;

const int N=2e5+10;
pii a[N];
int n;

bool check(int x){
	int tot=x-1;
	for(int i=1;i<=n;i++){
		int l=a[i].first,r=a[i].second;
		if(r>=tot&&l<=tot) tot--;
		if(tot==-1) return 1;
	}
	return 0;
}

void solve(){
	
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].first>>a[i].second;
	sort(a+1,a+n+1,[&](pii a,pii b)->bool{
		if(a.first!=b.first)return a.first>b.first;
		return a.second>b.second;
	});
	int l=0,r=n;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<r<<'\n';
	
}

int main(){
	int t;
	cin>>t;
	while(t--)solve();
	
	return 0;
} 

全部评论
贪心 关键思想就是如果当前mex = cur那么找所有l<=cur中r > cur的最小的就是答案
点赞 回复 分享
发布于 10-27 14:03 黑龙江

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务