【題解】ZeroJudge b151: NOIP2004 2.合并果子

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b151
【解題想法】排序 + Greedy

  • 先將每堆果子依數目進行排序,
    • (Python) list 從大到小排序,由 list 的尾端 pop,速度較快。
    • (C++) 藉由 priority_queue,從小到大排序,每次取出 top。
  • 每次依序取出最小的兩堆果子,合併後的值放回 list 或 priority_queue,重新排序,直到list 或 priority_queue中僅剩一個元素。
#include <iostream>
#include <queue>
using namespace std;
#define ll long long

int main() {
    ios_base:: sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll tmp;
    while (cin >> n){
        priority_queue<ll, vector<ll>, greater<ll> > pq;
        for (int i=0; i<n; i++){
            cin >> tmp;
            pq.push(tmp);
        }
        ll ans = 0, n1 = 0, n2 = 0;
        while (pq.size() > 1){
            n1 = pq.top();
            pq.pop();
            n2 = pq.top();
            pq.pop();
            pq.push(n1+n2);
            ans += n1 + n2;
        }
        cout << ans << '\n';
    }
    return 0;
}

Python code (credit: Amy Chou)

while True:
    try:
        n = int(input())
        a = list(map(int, input().split()))
        a.sort(reverse=True)
        ans = 0
        while (len(a) > 1):
            n1 = a.pop()
            n2 = a.pop()
            a.append(n1 + n2)
            a.sort(reverse=True)
            ans += (n1 + n2)

        print(ans)
    except:
        break
分享本文 Share with friends