POJ-3104 Drying

66 阅读 0 评论 44 点赞

我是靠谱客的博主平常香菇，这篇文章主要介绍POJ-3104 Drying，现在分享给大家，希望可以做个参考。

题目链接： http://http://poj.org/problem?id=3104

题意：你有n件湿度为a[i]的衣服需要晾干，每件衣服每分钟可以蒸干1个湿度，烘干机每分钟可以烘干k个湿度，烘干时不计蒸干，烘干机每次只能烘干一件衣服，问把这n件衣服晾干所需的最少时间。

思路：二分结果。

1.当k==1时，所需时间为n件衣服中湿度最大的值。

2.当k>1时，二分所需时间，求出结果。

参考代码：

#include <iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#define max(a,b) a>b?a:b
#define ll long long
#define inf 0x3f3f3f3f

using namespace std;
ll a[100010];
ll k,maxx;
int n;
bool check(ll x)
{
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]>x)//湿度>所需时间，用烘干机烘干
        {
            ll t=ceil((a[i]-x)*1.0/(k-1));//ceil()函数是求不小于给定实数的最小整数，如：ceil(2.3)=3
            ans+=t;
        }
    }
    if(ans<=x)
        return true;
    return false;
}
int main()
{
    while(~scanf("%d",&n))
    {
        maxx=0;
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            maxx=max(maxx,a[i]);
        }
        scanf("%lld",&k);
        if(k==1)
        {
            printf("%lldn",maxx);
            continue;
        }
        ll L=1,R=maxx,mid=(L+R)/2;
        while(L<R)
        {
            if(check(mid))
                R=mid;
            else
                L=mid+1;
            mid=(L+R)/2;
        }
        printf("%lldn",mid);
    }
    return 0;
}