Drying

标签：return cout int Drying mid ai include

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int const MAX = 1000 ;
int const INF = 9999999;
int n , k ;
// wash cloth ; 
/*
    题意：有n件衣服，每件衣服的含水量为ai单位，每分钟他们能自然脱水1单位，
    有一个脱水机，每次只能对一件衣服脱水，脱水量为k单位（脱水时不自然风干），
    问所有衣服全部风干的最小时间是多少？

    题解：首先能够想到的是可以二分查找全部自然风干的最少时间mid。但
    这一题不同的是在判断函数中用蛮力法判断mid是否满足条件是会出错。需要特殊处理。

    设某次二分出的一个值是mid：
    1、对于一件ai值小于 等于mid的衣服，直接晾干即可；
    2、对于一件ai值大于 mid值的衣服，最少的用时是用机器一段时间，晾
    干一段时间，设这两段时间分别是x1和x2，那么有mid=x1+x2，ai<=k*x1+x2，
    解得x1>=（ai-mid）/(k-1) ，所以对（ai-mid）/(k-1)向上取整就是该件衣服的最少用时。

*/
int a[MAX];
int case1 = 1 ;
int case2 = 1 ;
bool C(int x )
{
    // 判断C(x)是否满足条件; 
    int i ;
    int time = 0; 
    if(x==1)
    return true;
    for(i=1;i<=n;i++)
    {
        if(a[i]>x)
        {
             time+=(a[i]-x+k-2)/(k-1);//用向上取整函数ceil会WA，这里用K-2来向上取整   
        }
    }
    
    
    if(time>x)
    return true ;
return false ;
    
}

void solve()
{
    int left = 0 ;
    int right = INF ;
    while(right - left > 1)
    {
        int mid = (left+right)/2 ;
        if(C(mid))
        left = mid ;
        else
        right = mid ;

    }
    cout<<"sample input #"<<case2<<endl;
    cout<<right<<endl;
    case2++;
}
int main()
{
    int i ;
    cout<<"sample input #"<<case1<<endl;
    while(cin>>n)
    {
        if(case1!=1)
        cout<<"sample input #"<<case1<<endl;
        case1++;

    for(i=1;i<=n;i++)
    {
        cin>>a[i] ;   
    }
    cin >>k;
    sort(a+1,a+n+1);
    solve();
        
}



    return 0;  
}
/*
测试数据
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2*/

标签：return,cout,int,Drying,mid,ai,include
From： https://blog.51cto.com/u_15970235/6064101