Codeforces Global Round 17 C待更新

Codeforces Global Round 17 C待更新 Codeforces Global Round 17

时间也不早了，就介绍一下C题吧，明天更新D
题目意思就是：给你一个数n，然后再给n个a和n个b意思就是有钱排名i的人最多允许a个人比他还有钱，最多允许b个人比他穷（这个明明就是当代年轻人炫富的主要线路）
本来写的模拟，但是后来时间复杂度行不通O(n log(n))然后就想到了二分
注：这里二分的find用时O(n)然后二分用时O(log(n))所以×起来就是O(n log(n))啦O(∩_∩)O
接下来的就是代码啦！(部分注释使用了一个很奇怪的歪果语言）

//Author Chen1098
//Date Nov 26 23点20分 
#include
using namespace std;
int t,n,a[200005],b[200005];
bool find(int mid){ //O(n)
	int count=0;//at the worst part,you can't even invite yourself...
	for(int i=1;i<=n;i++){
		if(mid-1-a[i]<=count&&count<=b[i]) count++;//count means how many people you invite to the party
		//and if this if loop works than you can invite more people
	}
	if(count>=mid) return true;
	return false;
}
int main(){
	cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
        	cin>>a[i]>>b[i];
    	}
    	int l=0,r=n+1,mid;
    	while(r-l>=2){//log(n)
    		mid=(l+r)>>1;
    		if(find(mid)==true) l=mid;
    		else r=mid;
    	}
    	cout< 
谢谢观看！24小时内保证更新D题！（求点赞b(￣▽￣)d）
 有看不懂的记得问我哦！我时刻在线(* ^ _ ^ *)
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5634577.html