链接：https://vjudge.net/problem/POJ-3104#author=169074291
思路：二分法求解，注意有几个细节，最好是将烘干机人工看完每分钟掉水1和额外的每分钟掉水k-1，这样方便后面的计算，还有就是k=0的情况需要单独拿出来讨论，特别注意判断的时候返回true ub = mid，不要形成惯性思维。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5+1;
int n,k;
int a[maxn];
bool c(int d){
unsigned long long int minute = 0;
for(int i=0;i<n;i++){
int more = a[i] - d;
if(more>0){
minute += (more+k-1)/k; //将可整除和不可整除两种情况合二为一
}
if(minute>d)return false;
}
return true;
}
bool cmp(int &a,int &b){
return a>b;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&k);
k--; //分为自然掉水和额外的k-1掉水
if(k==0){//k=0的情况需要单独讨论
printf("%d\n",*max_element(a,a+n));
}
else{
int lb = 0;
int ub = *max_element(a,a+n);
sort(a,a+n,cmp);
while(ub-lb>1){
int mid = (ub+lb)/2;
if(c(mid))ub = mid;//一定注意true的时候到底是往哪边走
else lb = mid;
}
printf("%d\n",ub);
}
}
return 0;
}
