POJ - 3104：Drying（二分）

54 阅读 0 评论 36 点赞

我是靠谱客的博主粗暴歌曲，最近开发中收集的这篇文章主要介绍POJ - 3104：Drying（二分），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接
最让HSQ学长头疼的就是洗衣服了。洗完之后，每件衣服都有一定单位水分，在不使用烘干器的情况下，每件衣服每分钟自然流失1个单位水分，但如果使用了烘干机则每分钟流失K个单位水分。令人遗憾是HSQ所在的宿舍楼只有1台烘干机，而每台烘干机同时只能烘干1件衣服,请问要想烘干N件衣服最少需要多长时间？

输入
第一行输入N，表示有N件衣服，第二行输入N件衣服的水分ai，第三行表示烘干机每分钟烘干水分K
其中
1 ≤ N ≤ 100 000，1 ≤ ai ≤ 10^9,1 ≤ K≤ 10^9
输出
输出烘干N件衣服所需要的最短时间

样例输入

3
2 3 9
5

3
2 3 6
5
样例输出

题目描述

对n件衣服，分别含有不同单位的水分，每分钟可以晾干1个单位的水分，只有一台晾干机每分钟可以晾干水分k个单位，求晾干所有衣服至少需要多少时间
思路：对晾干衣服的时间进行二分搜索，大于mid的就需要使用晾干机，小于等于mid的就可以自己风干。值得一提的是计算时间的时候需要向上取整（因为你剩余水量可能小于每分钟能够吹干的水量，但是还是需要1分钟），在整数运算中a/b的向上取整为（a+b-1）/b
代码如下

#include <stdio.h>
#include <iostream>
#include <algorithm>
#define ll long long
#define Max_Size 100005

using namespace std;

ll k,a[Max_Size];
int n;

int main()
{
    int i;
    scanf("%d",&n);
    for(i = 0;i < n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&k);
    sort(a, a+n);
    if(k == 1)
    {
        printf("%lldn",a[n-1]);
        return 0;
    }
    ll l = 1, r = a[n-1], mid, time, ans;
    while(l <= r)
    {
        mid = (l + r) / 2;
        time = 0;
        for(i = 0;i < n;i++)
        {
            if(a[i] > mid)
                time += (a[i] - mid + k - 2) / (k - 1);		//向上取整，计算时间
            if(time > mid)
                break;
        }
        if(time <= mid)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    printf("%lldn",ans);
    return 0;
}