Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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-road W and east-road E, 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 roads W and E. Each aircraft arriving on W or E 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 of W and E 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.

For example, the above table represents the aircrafts arriving on the roads W and E at each time. At time 1, the aircrafts A₁, A₂ and A₃ receive the ranks 0, 1 and 2, respectively, and the aircrafts B₁ and B₂ receive the ranks 0 and 1, respectively. Then the control tower allows the aircraft B₁ on the road E to take off, and B₁ leaves the ground. At time 2, the aircrafts B₃, B₄, and B₅ receive the ranks 1, 2 and 3, respectively. Then A₁ on the road W is allowed to take off, and it leaves the ground. At time 3, the aircrafts A₄ and A₅ 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 integer n (1n5000) , the number of times. In the next n lines of each test case, the i-th line contains two integer numbers a_i and b_i, representing the number of arriving aircrafts on the road W and E, respectively, at time i, where 0a_i, b_i20.

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 13 3 20 32 06 0 11 11 21 11 16 0

Sample Output 

0 3 5

---

我們去二分答案, 然後我們去隨著時間累加兩邊的飛機數量, 同時記錄 lea,
lea 是用來當狀況數量大於答案的時候, 一次能消去的飛機數量

特別注意 sa+sb > lea, lea++, 因為此時這個狀態就可以全部離開, 如果沒有, 則會產生負飛機的情況

或者是換另一個方式講, 前一次的 0 0 中間可以出幾台

#include <stdio.h>
#include <stdlib.h>
int a[5005], b[5005], n;
int chk(int rank) {
    int i, sa = 0, sb = 0;
    int dif1, dif2, lea = 0;
    for(i = 0; i < n; i++) {
        sa += a[i];
        sb += b[i];
        if(sa > rank)   dif1 = sa - rank;
        else dif1 = 0;
        if(sb > rank)   dif2 = sb - rank;
        else dif2 = 0;

        if(dif1 + dif2 > lea)
            return 0;

        if(sa == 0 && sb > 0)
            sb--;
        else if(sb == 0 && sa > 0)
            sa--;
        else if(sa > 0 && sb > 0 && sa+sb > lea)
            lea++;
    }
    return 1;
}
int main() {
    int t, i;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d %d", &a[i], &b[i]);
        }
        int l = 1, r = 100000, m;
        while(l < r) {
            m = (l+r)>>1;
            if(chk(m))
                r = m;
            else
                l = m+1;
        }
        printf("%d\n", r-1);
    }
    return 0;
}