UVa 1450 - Airport
传送门
题意
有两个方向的飞机要起飞，一次只能飞一架，求任意时刻飞机最大编号的最小值。
思路
大家应该都能想到二分，但是验证的时候有一些要注意。
总的思路就是先储存着飞的飞机，如果有哪一方的飞机数大于mid了，让它飞，之后判断是不是都小于mid。
有一些情况：
-
某一时刻储存着的飞机不能多于目前的飞机总数。因为这时候可以飞完全部的飞机，不能继续飞了，也就不能存了。
-
当某一时刻有一方的飞机数为0的时候，另一方必须飞！如果这时候也存一下的话，可能把不能飞的飞机也算在了可以飞上面。
代码
#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
const int MAXN = 5000 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
struct POINT
{
int x, y;
}pit[MAXN];
int n;
bool Check(int mid)
{
int asum = 0, bsum = 0;
int rem = 0;
for (int i = 1; i <= n; i++)
{
asum += pit[i].x, bsum += pit[i].y;
if (asum > mid)
{
int t = min(rem, asum - mid);
rem -= t, asum -= t;
}
if (bsum > mid)
{
int t = min(rem, bsum - mid);
rem -= t, bsum -= t;
}
if (asum > mid || bsum > mid) return false;
if (asum && !bsum) asum--;
else if (bsum && !asum) bsum--;
else if (asum && bsum && asum + bsum > rem) rem++;
}
return true;
}
int main()
{
//freopen("input.txt", "r", stdin);
int T, i, j;
scanf("%d", &T);
while (T--)
{
int l = INF, r = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d%d", &pit[i].x, &pit[i].y);
r += pit[i].x + pit[i].y;
}
int mid;
l = 1;
while (l < r)
{
mid = l + ((r - l) >> 1);
if (Check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l - 1);
}
return 0;
}