前置知識

這題是「排序型貪心」的代表題，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 貪心與交換論證：NTUCPC Guide〈貪心法 II〉——「比較相鄰兩個交換前後的差」這套證法，它的例題之一正是本題（〈貪心法 I〉也用本題示範「直覺亂貪會錯」）；吳邦一《AP325》第 4 章 4.2.2「結構資料排序」的 Q-4-6 也是本題（教材 PDF 第 121～122 頁；Python 版第 4 章（I））。
• 自定義比較函式：語法書 11.6、11.7（相等必須回傳 false）。

簡潔題意

\(N\) 個物品疊在貨架上，第 \(i\) 個重 \(w(i)\)、要取用 \(f(i)\) 次。每取用一次某物品，就要把它上方所有物品抬起來，消耗的能量＝上方物品的總重。決定由上而下的擺放順序，讓總能量最小（\(N \le 10^5\)、\(w, f \le 1000\)；答案放得進 long long）。

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

• 子題組 1（\(10\) 分）：\(N = 2\)，且 \(f(1) = f(2) = 1\)。
• 子題組 2（\(20\) 分）：\(N = 3\)。
• 子題組 3（\(45\) 分）：\(N \le 1000\)，且每個物品的 \(f(i) = 1\)。
• 子題組 4（\(25\) 分）：\(N \le 10^5\)。

先把能量算對：由上而下累加「上方總重」

順序定了之後怎麼算總能量？由上而下一個一個看：取用第 \(i\) 層的物品要抬「它上面所有東西」，所以維護一個 above＝目前為止看過的物品總重，每到一個物品就把 above × f 加進答案，再把它的重量加進 above。範例 2 的 \((3, 2, 1)\)：\(0 \times 3 + 5 \times 2 + (5 + 4) \times 1 = 19\)。

long long above = 0, total = 0;           // above：目前上方物品的總重
for (int i : order) {                     // order：由上而下的物品編號
    total += above * f[i];
    above += w[i];
}

先拿下 30 分：N 很小就全部排列都試

子題組 1 只有兩個物品、取用各一次：誰在上面誰就要被抬，所以輕的放上面，答案就是較小的重量。子題組 2 有三個物品，\(3! = 6\) 種順序全部試一遍、取最小——用 next_permutation 把六種順序走完（11.4 同一個標頭檔）：

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

int main() {
    int n;
    cin >> n;
    vector<long long> w(n), f(n);
    for (int i = 0; i < n; i++) cin >> w[i];
    for (int i = 0; i < n; i++) cin >> f[i];

    vector<int> order(n);                     // 由上而下的順序：物品編號
    for (int i = 0; i < n; i++) order[i] = i;
    long long best = -1;
    do {                                      // 子題組 1、2：n ≤ 3，最多 6 種順序
        long long above = 0, total = 0;
        for (int i : order) {
            total += above * f[i];
            above += w[i];
        }
        if (best == -1 || total < best) best = total;
    } while (next_permutation(order.begin(), order.end()));
    cout << best << '\n';
    return 0;
}

\(N\) 一大這份程式就跑不完（\(N = 10\) 已經是 \(3628800\) 種順序）——這是正常的，逐筆給分之下子題組 1、2 的 \(30\) 分穩穩到手。

從 30 分到 100 分：相鄰兩件誰該在上面？

想知道最好的順序長什麼樣，先問一個小問題：相鄰的兩件物品 \(a\)、\(b\)，誰在上面比較好？ 把它們交換，其他物品誰在誰上面完全沒變，所以其他部分的能量一個都不會動——唯一變的只有 \(a\)、\(b\) 彼此之間那一份（圖 1）：

• \(a\) 在上：取 \(b\) 要抬 \(a\)，多花 \(w(a) \times f(b)\)。
• \(b\) 在上：取 \(a\) 要抬 \(b\)，多花 \(w(b) \times f(a)\)。

所以 \(w(a) \times f(b) < w(b) \times f(a)\) 時 \(a\) 就該在上面。這個判斷對任何相鄰兩件都成立：一個最好的順序裡，任兩個相鄰的物品都不能靠交換變得更好，也就是整排都照這個條件排好——把它寫成比較函式交給 sort 就是答案。

兩邊同除以 \(f(a) f(b)\)，條件就是 \(\dfrac{w(a)}{f(a)} < \dfrac{w(b)}{f(b)}\)：「重量除以取用次數」小的放上面——又輕又常拿的擺上面，直覺也說得通。實作用交叉相乘比，不用除法、沒有小數誤差。子題組 3 全部 \(f = 1\)，條件退化成 \(w(a) < w(b)\)：輕的放上面。

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

struct Item {
    long long w, f;
};

// a 該不該放在 b 上面：交叉相乘，不用除法
bool upper(const Item& a, const Item& b) {
    return a.w * b.f < b.w * a.f;
}

int main() {
    int n;
    cin >> n;
    vector<Item> item(n);
    for (int i = 0; i < n; i++) cin >> item[i].w;
    for (int i = 0; i < n; i++) cin >> item[i].f;

    sort(item.begin(), item.end(), upper);    // 由上而下的順序

    long long above = 0, total = 0;           // above：目前上方物品的總重
    for (const Item& it : item) {
        total += above * it.f;
        above += it.w;
    }
    cout << total << '\n';
    return 0;
}

排序 \(O(N \log N)\)，累加 \(O(N)\)。total 一定要 long long：\(10^5\) 個物品、重量與次數都頂到 \(1000\) 時，答案約 \(5 \times 10^{15}\)。比較函式用 < 不用 <=——兩個物品 \(w \times f\) 交叉相乘相等時誰上誰下能量一樣，但 <= 違反 11.7 的鐵則。

測過再交：範例裡重的都剛好比較常拿

範例 1 兩件取用次數相同、範例 2 的重量和次數同向遞增，「輕但很少拿、重但常拿」這種要靠比例判斷的情況，範例一次都沒出現。

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