Santa Claus and Tangerines
题目链接：http://codeforces.com/contest/752/problem/E
二分
显然直接求答案并不是很容易，于是我们将其转化为判定性问题：二分解x，验证是否能分成k个x。
于是要点就在于check函数：
由于奇偶的原因，每个ai分出来的并不是2的幂次（比如当ai=11，x=3时，可以将ai分成3部分5,3,3）。
但是稍作思考，可以发现还是与2的幂次有关：
例如，当ai=6:48，x=3时，
| ai | part1 | part2 | num |
| 6 | 3 | 3 | 2 |
| 10 | 5 | 5 | 2 |
| 11 | 5 | 6 | 3 |
| 12 | 6 | 6 | 4 |
| 20 | 10 | 10 | 4 |
| 21 | 10 | 11 | 5 |
| 22 | 11 | 11 | 6 |
| 23 | 11 | 12 | 7 |
| 24 | 12 | 12 | 8 |
| 40 | 20 | 20 | 8 |
| 41 | 20 | 21 | 9 |
| 42 | 21 | 21 | 10 |
| 43 | 21 | 22 | 11 |
| 44 | 22 | 22 | 12 |
| 45 | 22 | 23 | 13 |
| 46 | 23 | 23 | 14 |
| 47 | 23 | 24 | 15 |
| 48 | 24 | 24 | 16 |
若ai=44，因为40<=ai<=48，故num=16-（48-ai）;
若ai=38，因为24<=ai<40，故num=8.
这种做法的时间复杂度为O（n×lgA×lglgA）
代码如下：
#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;
typedef long long ll;
ll n,k,a[N],p[];
void init(){
p[]=;
for(ll i=;i<;++i)
p[i]=p[i-]<<;
}
bool check(ll x){
if(!x)return ;
ll sum=;
for(ll i=;i<n;++i){
ll t=a[i]/x;
ll up=*upper_bound(p,p+,t);
if(up*x-up/<=a[i])sum+=up-(up*x-a[i]);
else sum+=up/;
}
return sum>=k;
}
int main(void){
scanf("%I64d%I64d",&n,&k);
init();
for(ll i=;i<n;++i)scanf("%I64d",a+i);
ll l=,r=,mid;
while(l+<r){
mid=(r-l)/+l;
if(check(mid))l=mid;
else r=mid-;
}
if(check(r))printf("%I64d\n",r);
else if(check(l))printf("%I64d\n",l);
else printf("-1\n");
}