[SDOI2008] 烧水问题

题意

把 1kg 水平均分到 n 个杯子里，每杯初始都是 0 度。

你可以：

直接给某一杯加热
让两杯不同温度的水传热，直到它们温度相同

只要每杯水曾经达到过 100 度一次，就算完成。

问最少需要多少能量。

思路

先看一个直接模拟最优构造的版本：

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：教学版直接模拟最优构造过程。
// 我们按 1 -> 2 -> 3 -> ... -> n 的顺序处理：
// 1. 把当前这杯烧到 100 度；
// 2. 如果后面还有没烧开的杯子，就拿它和下一杯传热一次。
//
// 这样除了第一杯以外，后面的每一杯在第一次被烧开前都会先变成 50 度，
// 所以每次再补 50 度即可。

int n;
vector<long double> temp_arr;

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

    cin >> n;
    temp_arr.assign(n + 1, 0.0L);

    long double sum_delta = 0.0L;

    for (int i = 1; i <= n; i++) {
        // 先把第 i 杯补到 100 度。
        sum_delta += 100.0L - temp_arr[i];
        temp_arr[i] = 100.0L;

        // 再拿它给下一杯传热一次。
        if (i < n) {
            long double avg = (temp_arr[i] + temp_arr[i + 1]) / 2.0L;
            temp_arr[i] = avg;
            temp_arr[i + 1] = avg;
        }
    }

    long double ans = 4200.0L / n * sum_delta;
    cout << fixed << setprecision(2) << (double)ans << '\n';

    return 0;
}

这题最关键的观察是：

一杯还没烧开的水，如果已经有了正温度，再继续拿别的热水去“多预热几次”，其实并不划算。

因为这部分热量放在一个“还没完成任务”的杯子里，不如现在就把它直接烧开。一旦它自己达到了 100 度，它立刻就变成了一个新的热源，后面还能继续帮助别的杯子。

所以在最优方案里：

一杯水在第一次烧开前，没有必要被多次预热；
它最多只会接受一次传热。

而一次传热的最好情况，显然是：

一杯 100 度
一杯 0 度

传热后都变成：

text

于是可以得到结论：

第一杯只能自己从 0 烧到 100
其余每一杯在第一次烧开前，最多只能先到 50

所以总温度增量最少就是：

text

1
2100 + 50 * (n - 1)
= 50 * (n + 1)

每杯水质量是 1/n kg，升高 1 度需要：

text

14200 / n J

最终最小总能量：

text

1
24200 / n * 50 * (n + 1)
= 210000 * (n + 1) / n

代码

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#include <bits/stdc++.h>
using namespace std;

long long n;

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

    cin >> n;

    // 最优总“温度增量”是：
    // 第一杯从 0 烧到 100，需要 100 度；
    // 后面每一杯在最优情况下，第一次被烧开前最多只有 50 度，
    // 所以每杯再补 50 度即可。
    // 因而总温度增量为 100 + 50 * (n - 1) = 50 * (n + 1)。
    //
    // 每杯水质量是 1/n kg，升高 1 度需要 4200/n J。
    // 所以最小总能量为：
    // 4200 / n * 50 * (n + 1) = 210000 * (n + 1) / n。
    long double ans = 210000.0L * (n + 1.0L) / (long double)n;

    cout << fixed << setprecision(2) << (double)ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(1)$
空间复杂度： $O(1)$

总结

这题表面是操作设计，实际上关键只在一个结论：

每个后续杯子第一次烧开前，最多只值得先被预热到 50 度

抓住这一点后，整题就直接化成了一个闭式公式。

[SDOI2008] 烧水问题

目录

题意

思路

代码

复杂度

总结