飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17264

题意：就是给你两个轨道，分别为W，E然后有n个时刻，每个时刻回来pi和qi个飞机分别到W，E，且每个时刻能从W，E中起飞一辆飞机，但是刚飞到的飞机不能起飞。且每个机场当前的飞机编号为0~飞机数量-1。求两个机场一起最大编号的最小值。

分析：我的想法是二分+贪心+树状数组。

二分是为了求最小值，贪心和树状数组主要是判断用的。二分的边界就不用说了，我是直接用了l=1，r=100000，因为每个机场飞机最多的时候就只有100000，不过答案求出来要减一个1才行，因为是0开始的开始进入主题了；

假设当前判断的速度是x，则我们循环累计每个机场的数量，且每次存入树状数组（后面logn有用）。假设W机场每个时刻飞来ai两飞机。则当前W机场有sum（1。。。k）；假设我sum[0]，如果sum[0]>x了，那就说明前面的飞机必须起飞need=sum[0]-x辆了，然后就用到了贪心思想：因为每个时刻只能起飞一辆飞机，所以我们从1开始，枚举。。。而且我们用一个vis数组记录当前是否有飞机起飞过，有的话，就继续向后。当当前时间是m时。则我们可以用树状数组求的前面的还有没有飞机，如果有，我们就可以起飞，然后树状树状数组减1、、、如果当m=k的时候还不行说明方案不可行，直接返回false，如果可以那么继续循环，一直到最后。。。如果可以则返回true 更新最小值、、、这里哪里用了贪心呢，就是sum那里大于x时，因为我们从前面开始取的话，这样后面大于x时的选择空间更大。。。这样就可以了，复杂度为log（100000）*(n+2*n*logn)就是logn^2*n了吧，速度还是ok的，啪啪啪就可以AC了

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
using namespace std;
const int maxn=5*1234;
int C[2][maxn];
int lowbit(int x)
{
    return x&(-x);
}
int sum(int n,int idx)
{
    int sum=0;
    while(n>0)
    {
        sum+=C[idx][n];
        n=n-lowbit(n);
    }
    return sum;
}
int n,T;
void change(int i,int x,int idx)
{
    while(i<=n)
    {
        C[idx][i]=C[idx][i]+x;
        i=i+lowbit(i);
    }
}

struct he
{
    int a,b;
} JLJ[maxn];
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&JLJ[i].a,&JLJ[i].b);
    }
}
bool vis[maxn];
int summ[2];
int s[2];
bool check(int x)
{
    memset(vis,0,sizeof(vis));
    memset(C[0],0,sizeof(C[0]));
    memset(C[1],0,sizeof(C[1]));
    summ[0]=summ[1]=0;
    s[0]=s[1]=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=1; j++)
        {
            int tp=JLJ[i].a;
            if(j==1)
            {
                tp=JLJ[i].b;
            }
            summ[j]+=tp;
            if(summ[j]>x)
            {
                int need=summ[j]-x;
                int st=1;
                while(st<=need)
                {
                    if(s[j]==i)return 0;
                    if(vis[s[j]])
                    {
                        s[j]++;
                    }
                    else
                    {
                        int p=sum(s[j],j);
                        if(p>0)
                        {
                            change(s[j],-1,j);
                            st++;
                            vis[s[j]]=1;
                            s[j]++;
                        }
                        else
                        {
                            s[j]++;
                        }
                    }
                }
                summ[j]=x;
            }
            change(i,tp,j);
        }
    }
    return 1;
}
void play()
{
    int l=1,r=100000;
    int MIN=r;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            MIN=min(MIN,mid);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }

    }
    printf("%d\n",MIN-1);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}