【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c471
【解題想法】Greedy + Bubble Sort 【筆記】【筆記】【筆記】
- 考慮任兩個物品間的上下擺放關係：
- 物品 p1 = [w1, f1]；物品 p2 = [w2, f2]
- p1 放在 p2 的上方：w1 * f2
- p2 放在 p1 的上方：w2 * f1
- 物品兩兩比較後，依最省力的方式排序。
- 實作可以用 std::sort
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(pair<long long, long long> p1, pair<long long, long long> p2) {
return p1.first * p2.second < p1.second * p2.first;
}
int main() {
int N;
while (cin >> N) {
pair<long long, long long> p[N];
for (int i=0; i<N; i++) {
cin >> p[i].first;
}
for (int i=0; i<N; i++) {
cin >> p[i].second;
}
sort(p, p+N, cmp);
long long energy = 0;
long long cum_w = 0;
for (int i=0; i<N-1; i++) {
cum_w += p[i].first;
energy += cum_w * p[i+1].second;
}
cout << energy << endl;
}
return 0;
}
Python 程式碼 (credit: Amy Chou)
【提示】from functools import cmp_to_key：排序更有彈性。
from functools import cmp_to_key
while True:
try:
N = int(input().strip())
W = input().strip().split()
F = input().strip().split()
obj = [[int(w), int(f)] for w, f in zip(W, F)]
obj.sort(key=cmp_to_key(lambda a, b: a[0]*b[1] - b[0]*a[1]))
energy = 0
cum_w = 0
for i in range(N-1):
cum_w += obj[i][0]
energy += cum_w * obj[i+1][1]
print(energy)
except:
break