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

题意：给你n个服务，然后每个服务有时间di，和执行时间si，如果执行后的时间超过di，则惩罚值为max(0,最终的时间-di)，求最大两个惩罚值相加最小。

分析：二分套二分套二分，复杂度logn*n*logn*n。。。ORZ

第一个二分是确定两个和最小值用的，假设当前检测的值是x，则我们枚举每个服务，然后第二个二分，二分x的值，且l要大于等于x/2向上取整，r为x，这个是为了确定两个其中一个比较大的值，那么另一个值就可以为x-大的值，然后第三个二分，用来确定k应该插入到哪里去，假设大的值为i，小的值为j，则每个服务的d值都得家j，但是k的d值要加i，应该能理解，然后不是属于k的我们只要排序一次就够了，因为加了跟没加排序不变，然后用第三个二分把k插进去，按更新后的d从小到大，why??因为d越大的话，它的可用区域越大，贪心~所以把小的先处理，如果当前执行的任务超过了当前的d，如果是k，那就是说明k更新的值太小，所以第二个二分的l=mid+1，如果不是k，且超过了，那个r=mid-1，k太大~，如果可以，那么就说明当前方案是可以的，更新第一个二分。。。最后输出，over，啪啪啪，AC~

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#define LL long long
using namespace std;
const int maxn=5*123;
struct he
{
    int s,d;
} JLJ[maxn];
int T,n;
bool cmp(he a,he b)
{
    return a.d<b.d;
}
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d%d",&JLJ[i].s,&JLJ[i].d);
}
vector<he> V;
int isOK(int x,int y,int idx)
{
    int l=0;
    int r=V.size()-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(V[mid].d+y>JLJ[idx].d+x)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    V.insert(V.begin()+l, JLJ[idx]);
    int ip=l;
    int before=0;
    for(int i=0; i<V.size()-1; i++)
    {
        int tm=y;
        if(i==ip)tm=x;
        int s=V[i].s;
        int d=V[i].d+tm;
        if(s+before>d)
        {
            V.erase(V.begin()+ip);
            if(i==ip)return 1;
            return 2;
        }
        else before+=s;
    }
    V.erase(V.begin()+ip);
    return 0;
}
bool check(int x)
{

    for(int i=1; i<=n; i++)
    {
        V.erase(V.begin()+i-1);
        int l=x/2;
        int r=x;
        if(x%2!=0)l++;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int t=isOK(mid,x-mid,i);
            if(t==0)
            {
                V.insert(V.begin()+i-1,JLJ[i]);
                return 1;
            }
            if(t==1)
            {
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        V.insert(V.begin()+i-1,JLJ[i]);
    }
    return 0;
}
void play()
{
    sort(JLJ+1,JLJ+1+n,cmp);
    V.clear();
    for(int j=1; j<=n; j++)
    {
        V.push_back(JLJ[j]);
    }
    he a;
    a.s=0;
    a.d=2000000000;
    V.push_back(a);
    int l=0;
    int r=1000000;
    int MIN=1000000000;
    while(l<=r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
        {
            MIN=min(mid,MIN);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d\n",MIN);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

飞机票：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;
}

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

题意：就是给你n个需要处理的事情，第i个必须在li~ri完成，且数量是wi，完成时最大的速度最小是多少；

分析：求最大的速度最小我们可以使用二分来选择速度，但是怎么判断呢？果然还是太菜；其实可以根据时间来判断；具体怎么判断，时间递增，假设当前是j，则把所有左端点小于等于j的都压入到队列中，且按右端点排序（why?因为右端点越大我们可以在后面处理，所以这里贪心的想法），然后设当前还可以处理now个任务，当前碰到的是i，且任务数是w，我们可以判断下now和i的大小，把now和i都减去小的那个，如果now==0了，则退出了，因为不能再处理任务了，如果w不等于0则还没处理完，在压入到队列里。。。没一次j处理玩，可以判断下，如果最小的那个没处理完的r<=j则表明速度太小，返回false（why？？）因为下面大于j的时候已经不能处理它了，如果队列空了，且处理完了那么返回true，你懂得。。。。起先没有想到，，，太渣了。还是看别人的才反映过来。。。啪啪啪，就可以AC了~

/*
Author:Chieh
Because Of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=12345;
struct he
{
    int l,r,w;
    bool operator <(const he &a)const
    {
        return r > a.r;
    }
} JLJ[maxn];
priority_queue<he> q;
bool cmp(he a,he b)
{
    return a.l<b.l;
}
int n;
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d",&JLJ[i].l,&JLJ[i].r,&JLJ[i].w);
    }
}
bool check(int x)
{
    int i = 1, j = 0;
    while (!q.empty())
        q.pop();
    while (1)
    {
        while (i <= n && JLJ[i].l <= j)
            q.push(JLJ[i++]);
        int now = x;
        while (now != 0 && !q.empty())
        {
            he temp = q.top();
            q.pop();
            int m = min(now,temp.w);
            now -= m;
            temp.w -= m;
            if (temp.w != 0)
                q.push(temp);
        }
        j++;
        if (!q.empty() && q.top().r <= j)
            return false;
        if (q.empty() && i ==n+1)
            return true;
    }
}
void play()
{
    sort(JLJ+1,JLJ+1+n,cmp);
    int l=1;
    int r=1000000000;
    int MIN=r;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {

            r=mid-1;
            MIN=min(mid,MIN);
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d\n",MIN);
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

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

题意：就是给你一棵树，给你一个服务器，求在其余非叶子节点上放服务器，使任意的叶子节点到最近服务器的距离不超过k

分析：可以根据树形的性质来进行解决

具体步骤：用pair来存数据，如果first是1就是说有叶子节点没有服务器，如果first是2就说有服务器在；所以当我们搜到叶子节点的时候，返回(1,1),当搜到父子节点，我们对返回的子节点进行贪心选择，如果是1就选择距离最大的没有服务器的叶子节点，如果是2就选择最近的服务器，如果1+2的距离（1，为叶子节点最远距离，2为服务器最近距离）<=k那么就是可以访问到，则返回2，且服务器的距离要加1；如果>k那么就是说访问不到，那么我们要判断，如果1==k则必须架服务器了，不加则不满足条件，如果<k则返回叶子节点距离加1.一直递归到s节点，且s节点本身的2为0。。。ok复杂度为O（n-1)即边的数量；

啪啪啪。就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int n,T,s,k;
void init()
{
    scanf("%d%d%d",&n,&s,&k);
    for(int i=1; i<=n; i++)V[i].clear();
    int u,v;
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
int MIN;
pair<int,int> DFS(int now,int fa)
{
    int a1=-1;
    int a2=-1;
    if(now==s)a2=0;
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i];
        if(v==fa)continue;
        pair<int,int> p= DFS(v,now);
        if(p.first==1)
        {
            a1=max(a1,p.second);
        }
        else
        {
            if(a2==-1)a2=p.second;
            else
                a2=min(a2,p.second);
        }
    }
    if(a1==-1&&a2==-1)
    {
        return make_pair(1,1);
    }
    if(a1!=-1&&a2!=-1)
    {
        if(a1+a2<=k)
        {
            return make_pair(2,a2+1);
        }
        else
        {
            if(a1==k)
            {
                MIN++;
                return make_pair(2,1);
            }
            return make_pair(1,a1+1);
        }
    }
    if(a1==-1)
    {
        return make_pair(2,a2+1);
    }
    if(a1==k)
    {
        MIN++;
        return make_pair(2,1);
    }
    return make_pair(1,a1+1);
}
void play()
{
    MIN=0;
    DFS(s,0);
    printf("%d\n",MIN);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}