開啟章節選單

13242 Pool Filling

題目連結

題目敘述

有一個空的泳池，需要以指定的溫度裝滿水
為此，在泳池邊緣放置了一排水罐，編號從 0 開始
每個水罐中的水量及水溫各不相同
你可以將任意多個水罐的水倒入泳池
但所選的水罐必須是連續編號的

目標是在不溢出的前提下，至少倒入泳池容量一半的水
並使最終混合水溫儘可能接近目標溫度
且混合後的水溫不得超出目標溫度上下 5 度

我們假設，將兩份水混合時，混合後的溫度為各自溫度以水量為權重的加權平均值

例如，若有 5 個水罐，其內容如下：

水罐編號容量 (公升)溫度 (°C)
04523
12040
26722
310911
4956

例如，你可以倒入水罐 1、2、3，但不能只倒入水罐 1 和 3
若泳池容量足夠，倒入水罐 1、2、3 的總水量為 20 + 67 + 109 = 196 公升
混合後的溫度為 (20×40+67×22+109×11)/(20+67+109) = 17.719388 °C
​ 若沒有合適的方案則輸出 Not Possible

輸入格式

  1. 首行包含一個整數，表示待解決的問題數量。
  2. 對於每個問題，依序包含：
    • 一行包含兩個整數，分別為游泳池的最大容量與目標溫度。
    • 一行包含一個整數，表示水罐數量（不超過 3000）。
    • 接著 N 行，每行包含兩個整數，分別為該水罐的水量與溫度。

輸出格式

  • 對於每個問題，輸出一行：
    • 若可行，輸出兩個整數，分別為倒入游泳池的首個水罐編號與末尾水罐編號，使混合後的水溫與目標溫度的差值最小。
    • 若無法在不超出可接受溫度範圍（目標溫度 ±5°C）且至少填滿池塘一半容量的前提下達成，輸出 Not possible。
    • 若存在多種最優解，選擇編號最小的一組水罐。

解題思路

  1. 前綴和準備：為了快速計算任意連續區間的總體積與熱量，我們建立兩個前綴和陣列：

    • a[i]：表示第 1 到第 i 罐水的總熱量（體積×溫度加總）。
    • b[i]：表示第 1 到第 i 罐水的總體積。

  2. 暴力枚舉區間：使用兩層迴圈 i、j（1 ≤ i ≤ j ≤ n）枚舉所有可能的連續罐子區間。

    1. 計算區間 [i, j] 的總熱量 u = a[j] - a[i-1] 與總體積 d = b[j] - b[i-1]。

    2. 若 d > cap，表示超出池塘容量，可 break 提前終止內層迴圈，因為 j 再增加只會更大。

    3. 若 d >= ceil(cap/2)（至少填滿一半）且溫度誤差 |u/d - temp| <= 5，則比較當前誤差與歷史最小值，更新最優解。

  3. 結果輸出：若未找到合法區間，輸出 Not possible；否則輸出最優區間的左右端點。

程式碼

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int t; // t：測試案例的數量
    double cap, temp; // cap：池塘最大容量、temp：目標溫度
    cin >> t;
    while (t--) {
    	cin >> cap >> temp; // 讀取當前案例的池塘容量與目標溫度
        int n; cin >> n; // n：瓶子數量
        vector<pair<int, int>> v(n); // v[i] = {總熱量（volume*temperature），體積}
        vector<double> a(n+1), b(n+1); // a[i]：前 i 罐的總熱量前綴和；b[i]：前 i 罐的體積前綴和
        for (auto &i : v) cin >> i.se >> i.first, i.first *= i.second; // 讀入每個瓶子的體積與溫度，並計算該瓶的熱量後存入 v
        // i.second：體積, i.first：溫度；然後將 i.first 換成熱量 = 溫度 * 體積
        for (int i = 1; i <= n; i++) a[i] = a[i-1]+v[i-1].fi, b[i] = b[i-1]+v[i-1].second;
        // 建立前綴和：
        // a[i] = a[i-1] + v[i-1].first（累加熱量）
        // b[i] = b[i-1] + v[i-1].second（累加體積）

        pair<int, int> ans; // 儲存最佳解的左右端點 (0-base 索引)
        double mn = 1e9; // 初始化最小溫度誤差為極大值
        for (int i = 1; i <= n; i++) { // 枚舉所有可能的連續區間 [i, j]
            for (int j = i; j <= n; j++) {
                double u = a[j]-a[i-1], d = b[j]-b[i-1]; // 計算區間 [i, j] 的總熱量 u 與總體積 d
                double dif = abs(u/d-temp); // 計算混合後溫度與目標溫度的絕對誤差
                if (d > cap) break; // 若目前體積已經超出最大容量，內層迴圈後續 j 只會更大，可提前中斷
                if (dif <= 5 && dif < mn && d >= ceil(cap/2)) // 條件：至少填滿一半容量、溫度誤差不超過 5，且若誤差更小，更新答案
                    mn = dif, ans = {i-1, j-1}; // 記錄 0-base 索引範圍，i-1 為起始、j-1 為結束
            }
        }

        if (mn == 1e9) cout << "Not possible\n"; // 若 mn 未被更新，表示沒有符合條件的區間
        else cout << ans.fi << ' ' << ans.se << '\n';
    }
}

練習題

Pool Filling解答