POJ(3104)(Drying)

链接：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;
}