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 100000000000int 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);    }}