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