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