武器強化 題解

題目分析

我們有 $n$ 種武器與 $m$ 種強化材料。第 $i$ 種材料一開始適配武器 $p_i$，花費 $c_i$ 金幣就可以將它改成適配任意武器。目標是讓第 $1$ 種武器的材料數量嚴格大於其他所有武器，求最小金幣花費。

本題的關鍵在於：我們只需要關心最終每一種武器的材料數量，而不需要在意材料原本來自哪裡。因為任何材料都可以透過花費更改武器，我們可以把問題看成「重新分配材料」的過程，差別只在於原本就適配第 $i$ 種武器的材料，若要把它放到武器 $j$，需要花費 $c_i$（如果 $j = p_i$，則花費為 $0$）。

---

解題思路

枚舉目標數量

首先注意到第 $1$ 種武器的數量 $X$ 必須滿足 $X \ge 1$，且 $X$ 最多就是總材料數 $m$。我們可以嘗試枚舉最終武器 $1$ 的材料數量 $X$，並對每個 $X$ 計算達成條件的最小花費，最後取所有可能 $X$ 中的最小值。

對於一個固定的 $X$，條件是：

• 武器 $1$ 恰有 $X$ 個材料（多拿並沒有好處，因為我們只要求嚴格大於）
• 其他武器 $2 \sim n$ 的材料數量 $\le X-1$

強制階段：降低超出數量的武器

對於某個其他武器 $i$，如果它原本的材料數量 $cnt[i]$ 大於 $X-1$，我們就必須將其中 $cnt[i] - (X-1)$ 個材料移到其他武器（最有利的當然是移去武器 $1$，因為我們需要補足 $X$）。由於這些材料非移不可，我們自然要挑該武器中花費最小的那些材料來移動，這樣才能讓多付出的金幣最少。

這一步我們稱為「強制階段」，做完之後，所有其他武器的材料數量都會 $\le X-1$，同時武器 $1$ 的數量會暫時增加（因為移動過去的材料會加入武器 $1$）。

補足階段：讓武器 $1$ 到達 $X$

強制階段結束後，武器 $1$ 的暫時數量設為 $cur$。可能有三種情況：

1. $cur = X$：已經完美達標，不需要再做任何事。
2. $cur>X$：通常不會發生，因為強制階段最多只會把材料移到武器 $1$，使其數量增加，但如果初始 $cnt[1]$ 就超過 $X$，代表我們枚舉的 $X$ 不合理，此時這種情況可以直接跳過。（實作上讓 $X$ 從 $cnt[1]$ 開始列舉就可以避免）
3. $cur<X$：武器 $1$ 還需要再獲得 $X - cur$ 個材料。

要補足這些材料，來源就是那些在強制階段沒有被移走的剩餘材料（它們還留在原武器中，且目前原武器的數量已經 $\le X-1$，再拿走幾個也不至於違規）。因為這些材料都可以任意選擇，我們就把它們全部收集起來，依照花費排序，取最便宜的 $X - cur$ 個改到武器 $1$ 即可，這是顯然的貪心策略。

為什麼這樣是最優的？

• 在強制階段，我們只移走必須移的數量，而且每個武器內部都挑最便宜的移，這絕對不會比其他的移動方式差。
• 在補足階段，從全域還沒動的材料中挑最便宜的來補足，也是最佳策略。因為這些材料無論原本在哪個武器，花費都是固定的，且移動後對該武器的數量影響都在容許範圍內。
• 因此對一個固定的 $X$，這樣算出的花費就是真正的最小值。

---

算法說明

1. 讀入 $n, m$ 以及每種材料的 $p_i, c_i$。
2. 紀錄 $cnt[p_i]$ 為武器 $p_i$ 的初始材料數，並把 $c_i$ 存入對應武器 $p_i$ 的列表 cs[p_i]。
3. 對所有 $i=1 \sim n$，將 cs[i] 依照花費由小到大排序。
4. 令 $ans = \infty$。
5. 對於 $X$ 從 $\max(cnt[1], 1)$ 到 $m$：
   • 呼叫 calc(X) 得到花費，更新 $ans = \min(ans, calc(X))$。
6. 輸出 $ans$。

calc(X) 函數實作細節（對應參考程式碼）

cpp
复制
1ll calc(int aim) {
2    int cur_cnt = cnt[1];   // 武器1目前已擁有的材料數
3    ll res = 0;             // 累計花費
4    vector<int> tmp;        // 儲存所有剩餘材料的花費
5
6    // 處理其他武器
7    for (int i = 2; i <= n; i++) {
8        // 必須移走的數量：max(目前數量 - (aim-1), 0)
9        int buy = max((int)cs[i].size() - aim + 1, 0);
10        // 強制移走最便宜的 buy 個
11        for (int j = 0; j < buy; ++j)
12            res += cs[i][j];
13        cur_cnt += buy;     // 這些材料加入武器1
14
15        // 剩下的材料收集起來備用
16        for (int j = buy; j < cs[i].size(); ++j)
17            tmp.push_back(cs[i][j]);
18    }
19
20    // 補足武器1至 aim 個
21    sort(tmp.begin(), tmp.end());
22    for (int i = 0; i < aim - cur_cnt; i++)
23        res += tmp[i];
24
25    return res;
26}

這段程式碼中 buy 的計算使用了 cs[i].size() - aim + 1，原因是其他武器的允許上限是 aim - 1，因此需要移走的數量即為「目前數量 - (aim - 1)」。

---

時間複雜度分析

• 枚舉 $X$：$O(m)$ 次。
• 每次 calc：
  • 收集剩餘材料：$O(m)$
  • 排序 tmp：$O(m \log m)$
• 整體複雜度：$O\big(m \cdot m \log m\big) = O(m^2 \log m)$。

以本題 $n, m \le 1000$ 的限制，$m^2 \log m \approx 10^6 \times 10 = 10^7$，在時間限制內可以順利通過。

---

注意事項

• 花費 $c_i$ 最高可達 $10^9$，累加時需使用 long long（C++）等 64 位元整數型態，避免溢位。
• $X$ 的下界必須是 $\max(cnt[1], 1)$，因為武器 $1$ 的初始材料數已經有 $cnt[1]$ 個，且最終數量至少為 $1$。
• 當所有武器都不超過 $X-1$ 時，強制階段的 buy 會為 $0$，程式依然正確。

這道題目藉由「枚舉目標數量 + 雙階段貪心」的技巧，將看似複雜的分配問題轉化為清晰的計算，適合作為貪婪策略與複雜度分析的練習題。