Airport
A big city has an international airport handling 40 million passengers a year. But this is notorious as one of the most congested airports in the world. In this airport, there is only one landing strip as in the above figure. Therefore the landing strip is always crowded with a lot of aircrafts waiting for a takeoff. There are two ways, say west-roadW and east-roadE, to approach the landing strip. The aircrafts are waiting for a takeoff on the two roads as in the above figure.
At each time t, an arbitrary number of aircrafts arrive on the roadsW andE. Each aircraft arriving onW orE at time t receives a rank, which is equal to the number of the waiting aircrafts on the same road to precede it. Then the one ofW andE is chosen by a control tower, and the most front aircraft on the road leaves the ground. Given an information of the arriving aircrafts at times, we are concerned in the takeoff schedule of the control tower to minimize the maximum rank of the aircrafts.
| roads | ||
| W | E | |
| times | ||
| 1 | A1,A2,A3 | B1,B2 |
| 2 | B3,B4,B5 | |
| 3 | A4,A5 |
For example, the above table represents the aircrafts arriving on the roads W and E at each time. At time 1, the aircraftsA1,A2 andA3 receive the ranks 0, 1 and 2, respectively, and the aircraftsB1 andB2 receive the ranks 0 and 1, respectively. Then the control tower allows the aircraftB1 on the roadE to take off, and B1 leaves the ground. At time 2, the aircraftsB3,B4, andB5 receive the ranks 1, 2 and 3, respectively. ThenA1 on the roadW is allowed to take off, and it leaves the ground. At time 3, the aircraftsA4 andA5 receive the ranks 2 and 3, respectively. So the maximum rank of the aircrafts is 3, and this is the minimum of the maximum rank over all the possible takeoff schedules.
Input
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given on the first line of the input. The first line of each test case contains an integern(1
n
5000) , the number of times. In the next n lines of each test case, thei-th line contains two integer numbersai and bi, representing the number of arriving aircrafts on the roadW andE, respectively, at timei, where0
ai,bi
20.
Output
Your program is to write to standard output. Print exactly one line for each test case. The line contains the minimum of the maximum rank over all the possible takeoff schedules.
The following shows sample input and ouput for three test cases.
Sample Input
3
1
1 1
3
3 2
0 3
2 0
6
0 1
1 1
1 2
1 1
1 1
6 0
Sample Output
0
3
5
題目大意：W E 兩條跑道，兩個跑道裡面的飛機編号為0,1,2。。每個時刻隻能起飛任一跑道裡面的一架飛機，然後重新編号，每個時刻會有ai bi架飛機到達跑到後面，給你時間表，每個時刻到達的飛機數，求最大編号的最小值
分析：二分+判斷，另外自己的代碼一直WA，交了網上的所有标程都是WA，什麼情況。
#include <iostream>
#include <cstdio>
#define MAXN 5001
using namespace std;
int T,n,a[MAXN],b[MAXN];
bool check(int MAX)
{
int asum = 0,bsum = 0,time = 0;
for(int i = 1;i <= n;i++)
{
asum += a[i];
bsum += b[i];
if(asum > MAX)
{
time -= (asum - MAX);
asum = MAX;
}
if(bsum > MAX)
{
time -= (bsum - MAX);
bsum = MAX;
}
if(time < 0) return false;
if(asum + bsum > time)
if(asum && bsum == 0) asum--;
else
if(bsum && asum == 0) bsum--;
else time++;
}
return true;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int tota = 0,totb = 0;
for(int i = 1;i <= n;i++)
{
scanf("%d %d",&a[i],&b[i]);
tota += a[i];
totb += b[i];
}
int s = 1,t = max(tota,totb);
while(s < t)
{
int mid = (s + t)/2;
if(check(mid)) t = mid;
else s = mid+1;
}
printf("%d\n",s-1);
}
}