生產線 題解｜APCS 2021 年 11 月中高級 第 3 題

前置知識

這題的核心推導（為什麼需求大的位置要配時間小的機器）下面會從頭講；要先會的是兩個工具，同一個主題兩邊都有的，對照著讀會更快上手：

• 差分：NTUCPC Guide〈前綴和與差分〉的「差分」一節——要對一段 \([l, r]\) 的每一格都加 \(w\)，只在 \(l\) 記 \(+w\)、在 \(r + 1\) 記 \(-w\)，所有區間記完之後做一次前綴和，每一格的值就全部還原；\(m\) 個區間 \(O(n + m)\)。
• 排序後配對的貪心：NTUCPC Guide〈貪心法 I〉、吳邦一《AP325》第 4 章「單欄位資料排序」的例題 P-4-2、P-4-3（教材 PDF 第 124～126 頁；Python 版第 4 章）——要帶走的是「把兩邊各自排好序再一一配對，用交換論證說明為什麼不會更差」這個套路；排序直接用 sort。

簡潔題意

\(n\) 台機器排成一排，位置 \(1\) 到 \(n\)，機器 \(i\) 生產一單位資料要 \(t_i\) 單位時間。有 \(m\) 個工作，第 \(i\) 個工作要求位置 \(l_i\) 到 \(r_i\) 的每台機器各生產 \(w_i\) 單位。你可以任意調換機器的順序（哪台機器放在哪個位置），求所有工作做完的總時間最小是多少（\(1 \le n, m \le 2 \times 10^5\)，\(1 \le w_i, t_i \le 100\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(30\) 分）：\(n, m \le 100\)，且所有 \(w_i = 1\)。
• 子題組 2（\(30\) 分）：所有 \(w_i = 1\)。
• 子題組 3（\(40\) 分）：無額外限制。

先把問題換個說法：每個位置的總需求量

工作是對「位置」下的，不管哪台機器站在那裡。把位置 \(j\) 被所有工作要求的單位數加起來，叫它需求量 \(c_j\)；如果放在位置 \(j\) 的機器每單位要 \(t\) 時間，這個位置就貢獻 \(c_j \times t\)。總時間就是 \(\sum_j c_j \times (\text{放在 } j \text{ 的機器時間})\)——題目變成：\(n\) 個需求量、\(n\) 個時間，怎麼一一配對讓乘積總和最小。

大配小：需求大的位置配時間小的機器

猜想是：需求量最大的位置配上時間最小的機器、第二大配第二小、……。為什麼不會更差？假設某個配法裡，需求 \(c_a \ge c_b\) 的兩個位置分別配到時間 \(t_a > t_b\)（大需求配到了大時間），把兩台機器對調，總時間的變化是 \((c_a t_b + c_b t_a) - (c_a t_a + c_b t_b) = -(c_a - c_b)(t_a - t_b) \le 0\)，也就是對調之後不會變差。只要還有「大需求配大時間」的一對就一直對調，最後一定變成「需求由大到小、時間由小到大」一一對應的樣子，而且過程中總時間從沒變大——所以這個配法就是最小的。

程式上就是：need 由小到大排、t 由小到大排，need[j] 配 t[n + 1 - j]（一個從頭、一個從尾）。

先拿下 30 分：逐格加需求量

子題組 1 的 \(n, m \le 100\)，每個工作直接把 \(l_i\) 到 \(r_i\) 每一格都加上 \(w_i\) 就好。

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

const int MAX_N = 200000;
long long need[MAX_N + 1];       // need[j] = 位置 j 總共要生產幾單位
long long t[MAX_N + 1];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int l, r, w;
        cin >> l >> r >> w;
        for (int j = l; j <= r; j++) need[j] += w;   // 這個工作蓋到的每個位置都加 w
    }
    for (int j = 1; j <= n; j++) cin >> t[j];
    sort(need + 1, need + n + 1);                    // 需求量由小到大
    sort(t + 1, t + n + 1);                          // 機器時間也由小到大
    long long total = 0;
    for (int j = 1; j <= n; j++) {
        total += need[j] * t[n + 1 - j];             // 需求最小的配時間最大的、需求最大的配時間最小的
    }
    cout << total << endl;
    return 0;
}

逐格加最多 \(n \times m\) 次：子題組 1 是 \(10^4\)，一瞬間；但 \(n = m = 2 \times 10^5\)、工作又都很長時是 \(4 \times 10^{10}\)，本站實測長區間的測資要 \(4\) 到 \(16\) 秒，時限 \(1\) 秒。子題組 1 的 \(30\) 分穩穩到手。

總時間要用 long long：一個位置的需求量最多 \(m \times 100 = 2 \times 10^7\)，乘上時間最多 \(100\) 是 \(2 \times 10^9\)，\(n\) 個位置加起來最多 \(4 \times 10^{14}\)，遠超過 int 的 \(2147483647\)（估算方法見語法書 2.9）。

從 30 分到 100 分：差分

慢的只有「逐格加」。差分把每個工作變成兩筆記錄：diff[l] += w、diff[r + 1] -= w；全部記完之後從左到右做前綴和，need[j] = need[j - 1] + diff[j]——走到 \(l\) 時加進來的 \(w\) 會一路帶到 \(r\)，到 \(r + 1\) 被扣掉，正好就是「\(l\) 到 \(r\) 每格加 \(w\)」（圖 1）。\(m\) 個工作 \(O(m)\)、還原 \(O(n)\)，加上排序整題 \(O(n \log n + m)\)，最大測資本站實測 \(0.1\) 秒。

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

const int MAX_N = 200000;
long long diff[MAX_N + 2];       // 差分陣列
long long need[MAX_N + 1];       // need[j] = 位置 j 總共要生產幾單位
long long t[MAX_N + 1];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int l, r, w;
        cin >> l >> r >> w;
        diff[l] += w;                                // 從位置 l 開始每格多 w
        diff[r + 1] -= w;                            // 到位置 r 為止，r + 1 之後要扣回來
    }
    for (int j = 1; j <= n; j++) need[j] = need[j - 1] + diff[j];   // 前綴和還原成每格的需求量
    for (int j = 1; j <= n; j++) cin >> t[j];
    sort(need + 1, need + n + 1);                    // 需求量由小到大
    sort(t + 1, t + n + 1);                          // 機器時間也由小到大
    long long total = 0;
    for (int j = 1; j <= n; j++) {
        total += need[j] * t[n + 1 - j];             // 需求最小的配時間最大的、需求最大的配時間最小的
    }
    cout << total << endl;
    return 0;
}

diff 要開到 \(n + 2\) 格：\(r = n\) 的工作會寫 diff[n + 1]。

測過再交：範例的機器時間都是 \(1\) 到 \(n\) 排好的

兩個範例的 \(t\) 都剛好是 \(1, 2, \ldots, n\) 遞增、工作也都很短；沒蓋到的是：只有一台機器、每個工作都蓋滿全部位置（怎麼擺都一樣）、有位置完全沒被要求（需求量 \(0\)）、機器時間亂序（驗真的有排序）、工作的右端點是 \(n\)（驗差分的 \(r + 1\) 那格）、以及最大的 \(n\)、\(m\) 配最長的工作（驗 long long 和速度）。

六筆都親眼看過正確，這題就穩了。