奶牛晒衣服

题意

有 n 件衣服，每件衣服初始湿度为 w_i。

每过 1 秒，所有衣服都会自然减少 a 点湿度。同时还可以再用 1 秒烘衣机，让某一件衣服额外减少 b 点湿度。烘衣机同一时间只能烘一件衣服。

要求求出弄干所有衣服的最少时间。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
int n;
long long a, b;
long long w[MAXN];

bool canFinish(long long t) {
    long long machine = 0;
    for (int i = 1; i <= n; i++) {
        long long left = w[i] - a * t;
        if (left <= 0) continue;
        machine += (left + b - 1) / b;
        if (machine > t) return false;
    }
    return machine <= t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> a >> b;
    long long maxW = 0;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) {
        if (w[i] > maxW) maxW = w[i];
    }

    long long limit = (maxW + a - 1) / a;
    for (long long t = 0; t <= limit; t++) {
        if (canFinish(t)) {
            cout << t << '\n';
            return 0;
        }
    }

    // 理论上一定会在自然风干上界内找到答案，这里只是兜底。
    cout << limit << '\n';
    return 0;
}

朴素解从小到大枚举时间，检查这个时间够不够把所有衣服弄干。虽然直观，但正式做法需要利用单调性。

设 check(T) 表示“用 T 秒是否能把所有衣服弄干”。

如果 T 秒能做到，那么更长的时间只会让自然风干更多，烘衣机可用时间也更多，所以一定也能做到。于是 check(T) 具有单调性，可以二分最短时间。

对于固定时间 T：

每件衣服先自然风干 a * T 点。
如果还剩 left = w_i - a * T 点湿度，就需要烘衣机再烘 ceil(left / b) 秒。
把所有衣服需要的烘衣机秒数加起来。
如果总烘衣机秒数不超过 T，说明这个时间可行。

这张表展示样例中几个时间的检查结果。

时间 `T`	自然风干后剩余	需要烘衣机秒数	是否可行
`0`	`1,2,3`	不够	否
`1`	`0,0,1`	`1`	是

因此最少时间是 1。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500000 + 5;
int n;
long long a, b;
long long w[MAXN];

bool canFinish(long long t) {
    long long machine = 0;
    for (int i = 1; i <= n; i++) {
        long long left = w[i] - a * t;
        if (left <= 0) continue;
        machine += (left + b - 1) / b;
        if (machine > t) return false;
    }
    return machine <= t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> a >> b;
    long long maxW = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        if (w[i] > maxW) maxW = w[i];
    }

    long long l = 0, r = (maxW + a - 1) / a;
    while (l < r) {
        long long mid = (l + r) / 2;
        if (canFinish(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << l << '\n';
    return 0;
}

复杂度

每次检查需要扫描所有衣服，复杂度 $O(n)$ 。
二分时间的次数是 $O(log maxW)$ 级别。
总时间复杂度 $O(n log maxW)$ 。
空间复杂度 $O(n)$ 。

总结

这题是标准的二分答案模型。

关键在于把“时间够不够”写成一个单调检查函数。给定时间后，先算自然风干，再把剩余湿度换算成烘衣机秒数，最后看总秒数是否超过 T。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析