思路分析

一看范围：$n \le 10^6$，所以要用 $O(n)$ 或 $O(n\times log n)$ 的算法。 $O(n)$ 的算法不好想，所以我们尝试$O(n\times log n)$ 的算法，也就是二分。 证明：如果进入到 $n$ 号房间可以返回，说明在解在$[n,10^6]$ 范围；否则解在 $(0,n)$ 范围。符合单调性，所以二分成立。 这道题二分房间号，判断 $ans$ 号房间是否成立，之后二分。

code

#include<bits/stdc++.h>
using namespace std;
struct room{
	int id,t,boom;
}a[1000005];
bool cmp(room a,room b){
	return a.id<b.id;
}
bool judge(int ans){
	for(int i=0;a[i].id<=ans;i++){
		if(2*(ans-a[i].id)>=a[i].t)	return 0;//如果返回时间大于崩塌时间，答案不成立
	}
	return 1;
}
string main(){
	int l=0,r=1e6,ans=-1;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].id>>a[i].t;
	}
	sort(a,a+n,cmp);//排序
	while(l<=r){
		int mid=(l+r)>>1;
		bool f=judge(mid);
		if(f){//如果合法
			ans=mid;//记录答案
			l=mid+1;//往大找
		}else{
			r=mid-1;//往小找
		}
	}
	cout<<ans;
	return "抄题解可耻";
}

进食后人/警钟撅烂

都是二分了，别忘了排序!!!