LA 4725 (二分) Airport

题意：

有W、E两个跑道，在每个时刻每个跑道的飞机都从0开始编号，而且每个时刻都有W_i和E_i架飞机到达这两个跑道。而且每个时刻只能选择一个跑道的一架飞机起飞。问如何选择才能使得飞机的最大编号最小。(每个时刻算编号时是在飞机起飞之前的)

思路：

又是一个最大值最小的问题，可以用二分，不过怎么二分我没有想到。

参考的别人的代码：http://blog.csdn.net/u011345136/article/details/17793415

起飞的决策是这样的：

如果一条跑道是空的，另一条跑道有飞机，那么一定是选择有飞机的那条跑道起飞。

如果两条跑道都有飞机，把能起飞的次数加一记录下来。

假设最大编号为k，如果两个跑道比k多出来的那些飞机比能起飞走的次数还多，说明最大编号就比k大了，这时就不行。

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 5000 + 10;
 8 const int INF = 150000;
 9 int a[maxn], b[maxn], n;
10 
11 bool check(int k)
12 {
13     int A = 0, B = 0, aa, bb, sum = 0;    //A B分别是两条跑道的飞机数量
14     for(int i = 0; i < n; ++i)
15     {
16         A += a[i];
17         B += b[i];
18         aa = max(A - k, 0);
19         bb = max(B - k, 0);
20         if(aa + bb > sum)    return false;
21         if(A == 0 && B)    --B;
22         else if(B == 0 && A)    --A;
23         else if(A && B && A + B > sum)    ++sum;    //A + B <= sum说明两条跑道都没有飞机了
24     }
25     return true;
26 }
27 
28 int main(void)
29 {
30     #ifdef LOCAL
31         freopen("4725in.txt", "r", stdin);
32     #endif
33 
34     int T;
35     scanf("%d", &T);
36     while(T--)
37     {
38         scanf("%d", &n);
39         for(int i = 0; i < n; ++i)
40             scanf("%d%d", &a[i], &b[i]);
41 
42         int l = 0, r = INF;
43 
44         int ans;  
45         while (l <= r)
46         {  
47             int mid = (l + r) >> 1;  
48             if (check(mid))
49             {  
50                 ans = mid;  
51                 r = mid - 1;  
52             }  
53             else l = mid + 1;  
54         }  
55         printf("%d
",ans-1);  
56 
57     }
58 
59     return 0;
60 }

代码君