我是靠谱客的博主 平常香菇,这篇文章主要介绍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;
}

最后

以上就是平常香菇最近收集整理的关于POJ-3104 Drying的全部内容,更多相关POJ-3104内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(45)

评论列表共有 0 条评论

立即
投稿
返回
顶部