Drying POJ - 3104 二分 最优

时间：2023-12-23 19:07:07

题意：有N件湿的衣服，一台烘干机。每件衣服有一个湿度值。每秒会减一，如果用烘干机，每秒会减k。问最少多久可以晒完。

题解：二分。首先时间越长越容易晒完。

　　　　其次判定函数可以这样给出：对于答案 X，每一个湿度大于X的衣服都要被烘干。所以可以直接统计烘干机被用的总时间，如果其大于X则返回0.

　　　　注意向下取整细节。

#define _CRT_SECURE_NO_WARNINGS

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<cmath>

#include<cstdio>

#include<string>

#include<stack>

#include<ctime>

#include<list>

#include<set>

#include<map>

#include<queue>

#include<vector>

#include<sstream>

#include<iostream>

#include<functional>

#include<algorithm>

#include<memory.h>

//#define INF 0x3f3f3f3f

#define eps 1e-6

#define pi acos(-1.0)

#define e exp(1.0)

#define rep(i,t,n)  for(int i =(t);i<=(n);++i)

#define per(i,n,t)  for(int i =(n);i>=(t);--i)

#define mp make_pair

#define pb push_back

#define mmm(a,b) memset(a,b,sizeof(a))

//std::ios::sync_with_stdio(false);

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

void smain();

#define ONLINE_JUDGE

int main() {

    ios::sync_with_stdio(false);

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

    long _begin_time = clock();

#endif

    smain();

#ifndef ONLINE_JUDGE

    long _end_time = clock();

    printf("time = %ld ms.", _end_time - _begin_time);

#endif

    return ;

}

const int maxn = 1e5 + ;

int a[maxn];

int n, k;

int l, r, mid;

bool check(int x) {

    int now = ;//time for radiator

    rep(i, , n) {

        if (a[i] > x) {

            now += (a[i] - x - ) / (k - ) + ;//k-1&&ceiling/consider integer

            if (now > x)return ;

        }

    }

    return ;

}

void Run() {

    l = , r = ;

    r = *max_element(a + , a +  + n);

    if (k == ) { cout << r<<endl; }

    else {

        while (l <= r) {

            mid = l + r >>;

            if (check(mid))r = mid - ;

            else  l = mid + ;

        }

        cout << l << endl;

    }

}

void smain() {

    cin >> n;

    rep(i, , n)cin >> a[i];

    cin >> k;

    Run();

}

相关文章