POJ3104--Drying

59 阅读 0 评论 39 点赞

我是靠谱客的博主长情时光，最近开发中收集的这篇文章主要介绍POJ3104--Drying，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：Jane洗完了一些衣服，每件衣服有一定的数量，现在她有一台烘干机，烘干机每分钟可以烘干k数量的水，而风干每分钟只能蒸发1数量的水。求如何使用烘干机，使得这些衣服全部变干的时间最短。

分析：二分答案。当mid>x[i]时，说明多余的水量需要用烘干机来烘干，而每分钟烘干多余的水量其实为k-1，k-1是因为，我们是假设在mid的时间里所有衣服相当于一直被风干，然后，在这mid的可以采用烘干的方式烘干所有多余的水量，如果烘干次数（等价于时间，一次烘干需要一分钟）大于mid，则说明答案小了，需要将搜索下界变大。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 111111;

long long n;
long long x[maxn];
long long k, ans;

bool C(long long tot) {
    long long sum = 0;
    for(int i = 0; i < n; i++) {
        if(x[i] > tot) {
            long long t = ceil((x[i]-tot)*1.0/(k-1));
            sum += t;
        }
    }
    if(sum <= tot) return true;
    else return false;
}

int main() {
    while(~scanf("%lld", &n)) {
        long long mx = 0;
        for(int i = 0; i < n; i++) {
            scanf("%lld", &x[i]);
            mx = max(mx, x[i]);
        }
        scanf("%lld", &k);
        if(k == 1) {
            printf("%lldn", mx);
            continue;
        }
        long long L = 0, R = mx;
        while(L < R) {
            long long mid = (L+R)/2;
            if(C(mid)) R = mid;
            else L = mid+1;
        }
        printf("%lldn", R);
    }
    return 0;
}