【題解】ZeroJudge c471: apcs 物品堆疊 (Stacking)

【題目敘述】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
分享本文 Share with friends