cf-348A 2分暴力

cf-348A 二分暴力

http://codeforces.com/problemset/problem/348/A

由题意直接对答案进行二分查找  知道找到满足条件的最小的ans

wa了一次  是因为没有对数组排序

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define MAX 100010
#define INF 100000000000
int a[MAX],n;
int cmp(int a,int b)
{
    return a>b;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        sort(a,a+n,cmp);  //排序 贪心
        long long r=INF,l=0,ans=(r+l)/2;
        while(l<r)
        {
            long long left=ans,i;
            for(i=0;i<n;i++)
            {
                if(a[i]>ans)  //如果需要的盘数大于ans 则ans不符合
                {
                    l=ans+1;
                    ans=(r+l)/2;
                    break;
                }
                else
                {
                    left=left-(ans-a[i]); //剩余需要主持的盘数
                    if(left<=0)  //ans符合要求
                    {
                        r=ans;
                        ans=(r+l)/2;
                        break;
                    }
                }
            }
            if(i==n&&left>0)
            {
                l=ans+1;
                ans=(r+l)/2;
            }
        }
        printf("%I64d\n",ans);
    }
}