题意：有一个机场只有一条起飞跑道，有两个入口E，W，每时刻只能有一架飞机起飞，而每时刻也都会有一些飞机进入入口E，W，在任意时刻，E通道和W通道里的飞机分别
从0开始编号，你的任务是在每个时刻选择一架飞机起飞，使得任意时刻的飞机的最大编号最小
思路：又是最大值的最小值，二分处理，问题是如何判断是否满足条件，贪心模拟显然是麻烦的，先想一下不满足的情况是什么吧，如果我们需要起飞的飞机使得最大的值不大于K的次数大于我们可以起飞的次数，那么显然这个值是不行的，我们可以用一个数记录我们可以起飞的次数，特殊情况的时候特殊处理，比如 L == 0 || R == 0, L，R分别代表此时刻W，E机场的飞机个数
#include#include #include #include using namespace std; const int MAXN = 6000; struct plane{ int a,b; }arr[MAXN]; int n; bool check(int k){ int l = 0,r = 0,sum = 0; for (int i = 0; i < n; i++){ l += arr[i].a; r += arr[i].b; int ll = max(l-k,0); int rr = max(r-k,0); if (ll + rr > sum) return false; if (l == 0 && r > 0) r--; else if (r == 0 && l > 0) l--; else if (l && r && l + r > sum) sum++; } return true; } int main(){ int t; scanf("%d",&t); while (t--){ scanf("%d",&n); int Max = 0; for (int i = 0; i < n; i++){ scanf("%d%d",&arr[i].a,&arr[i].b); Max += max(arr[i].a,arr[i].b); } int l = 1, r = 5000*20; int ans; while (l <= r){ int mid = (l + r) >> 1; if (check(mid)){ ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n",ans-1); } return 0; }