Poj 3104: Drying

poj3104.md

Poj 3104: Drying

題目

分析

最大值最小化 => 二分搜

竟然大玩文字陷阱… decreases by k this minute … 這是說 radiator 的烘乾速率是 k-1 per minute

正負相關性判定

bool C(s) = 可否在時間 t 以內曬乾所有衣服

實作時，改成計算 t 秒的自然曬乾以後，剩下的衣服可不可能用 radiator 在 t 秒內（即 t 次）烘乾。

而 C(x) 表是

0 0 0 1 1 1 1 1

這種形式，而我們的目標是尋找第一個 1 在哪

上下界判定

這題是最小值最大化，使用 (lb, ub]

上界發生在 k = 1 時，即 radiator 根本沒有作用，答案是 max(a[i])

下界為 1，不管怎麼說，一定要至少 1 秒才可能弄乾所有衣服

事實上，可以直接把上下界設成 INF=0x3f3f3f3f, 0，只要保證邊界的性質 (lb, ub]， 反正二分搜縮減範圍的速度很快，0 ~ 2 ^ 32 大約也只要 30 次左右就可求出答案。

// (lb, ub]
int lb = 0;
int ub = *max_element(a, a + N);

while (ub - lb > 1) {
    int mid = (lb + ub) / 2;
    if (C(mid)) ub = mid;
    else lb = mid;
}

答案為 ub

其它

因實作 C(t) 時，會使用除以 K-1，所以得對 K = 1 的情況做特殊判斷

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

int N, K;
int a[100000];

bool C(int t) {
    long long cnt = 0;
    for (int i = 0; i < N; i++) {
        if (a[i] > t) {
            cnt += (a[i] - t) / (K-1);
            if ((a[i] - t) % (K-1) != 0)
                cnt++;
        }
    }

    return cnt <= t;
}

int solve() {
    // special case K = 1
    if (K == 1)
        return *max_element(a, a + N);

    // (lb, ub]
    int lb = 0;
    int ub = *max_element(a, a + N);

    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (C(mid)) ub = mid;
        else lb = mid;
    }

    return ub;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &a[i]);
    scanf("%d", &K);

    printf("%d\n", solve());

    return 0;
}