题意

Jane有件带水没干衣服,每件带单位的水,自然状态下每分钟每件衣服会干掉一单位的水,为了让衣服更快的干掉,Jane决定使用吹风机吹衣服。Jane每分钟都可以选择其中一件衣服对其使用吹风机,在吹风机和自然环境的共同作用下,一件衣服每分钟可以干掉单位的水,问让衣服全部干掉最少需要多少分钟。

思路

二分+检验

对于这件衣服,我们记不用吹风机的情况下自然干需要分钟,很容易想到我们可以直接从枚举,判断每种情况能否让衣服全部干掉。但是这样太耗费时间,所以我们可以做个优化,对干衣服的时间做一个二分查找,直到刚好能让全部衣服干掉为止

如何判断能否在分钟内让衣服全部干掉?

首先,在自然环境的作用下,分钟内每件衣服都干掉了单位的水,所以那些初始带水量小于等于的衣服就全部自然干掉了。
然后再看无法自然干掉的水,经过分钟后一件衣服剩余的水为个单位,单独在吹风机的作用下,一件衣服可以一分钟减少单位的水。由于一分钟内只能选择一件衣服对其使用吹风机,我们就可以算出,让一件无法自然干的衣服干掉,需要用吹风机吹分钟(向上取整)。然后我们把每一个求和,如果求和的结果大于,就说明时间不够,无法让衣服全部干掉

代码

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int n;  //衣服的数量
int a[100005];   //衣服自然干需要的时间
int k;  //用了吹风机以后的干水速度
/**
 * @brief 判断在time分钟内能否让衣服全部干掉
 * @param time 所用的时间
 * @return bool
 */
bool judge(int time) {
    int leftTime = time;    //剩余的能使用吹风机的时间
    for (int i = 0; i < n; ++i) {
        if (a[i] <= time)continue;
        //在一件不能干的衣服上使用吹风机
        //耗费的时间为 (初始水量-自然干掉的水)/ 吹风机能带走的水 向上取整
        //ps:吹风机能带走的水为k-1,因为是吹风机和自然干的共同作用导致一分钟能干k的水
        leftTime -= ceil((a[i] - time) / (k - 1.0));
        //如果时间变成负数代表没办法让衣服全部干掉
        if (leftTime < 0)return false;
    }
    return true;
}

int main() {

    scanf("%d", &n);
    int maxA = 0; //单件衣服自然干需要的最长时间
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        maxA = max(a[i], maxA);
    }
    scanf("%d", &k);

    //如果k=1直接全部自然干
    if (k == 1) {
        printf("%d", maxA);
        return 0;
    }
    //二分检验
    int left = 1, right = maxA, mid;
    while (left <= right) {
        mid = (left + right) >> 1;
        if (judge(mid))right = mid - 1;
        else left = mid + 1;
    }
    //最后一次judge为true会让right=mid-1,所以输出right+1
    //如果输出mid,可能会输出最后让judge为false的mid(可能,我没仔细看)
    printf("%d", right + 1);
}