HOJ 003 童話故事

[二分搜]

#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define LL long long int
#define MM 1000000
#define MAX(a,b) (((a)>(b)) ? (a):(b))
LL N;
LL VAL[MM];
LL DIS[MM];
bool Check(LL a)
{
    //printf("Check(%I64d)\n",a);
    LL Center=0;
    bool OK=true;
    for(int lx=0;lx<N;lx++)
        if(VAL[lx]>=a)
            Center+=MAX(VAL[lx]-a-DIS[lx],0);

    for(int lx=0;(lx<N)&&OK;lx++)
    {
        if(VAL[lx]<a)
            Center-=a-VAL[lx]+DIS[lx];
        OK=(Center>=0);
    }
    return OK;
}
int main()
{
    scanf("%I64d",&N);
    LL min=-1,max=0,mid;
    for(LL lx=0;lx<N;lx++)
    {
        scanf("%I64d %I64d",&DIS[lx],&VAL[lx]);
        if((min==-1)||(min>VAL[lx])) min=VAL[lx];
        max+=VAL[lx];
    }
    max/=N;
    while(min<max)
    {
        //printf("min=%I64d max=%I64d\n",min,max);
        if(min==max-1)
        {
            if(Check(max))
                min=max;
            break;
        }
        mid=(min+max)>>1;
        if(Check(mid))
            min=mid;
        else
            max=mid-1;
    }
    printf("%I64d\n",min);
    return 0;
}