[Algorithm Elementrary]合并果子

Thinking Process

这题很简单。举个例子就能知道思路。
三个果子重量分别为10、5、7.合并两次，由于第二次合并出来的值一定是10+5+7=22所以只要第一次合并出来的值小就可以了，即我们取三者之中的最小值5和7。根据这个思路就可以做出这道题。需要注意的是每一次的合并值都得纳入考虑!!

first method

use 2 queues to record original value and merged value.Get two minimums through compared the front value of queues.

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
queue<int> a;
queue<int> b;
int c[1000010];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> c[i];
    sort(c, c + n);
    for(int i = 0;i < n; i ++) a.push(c[i]);
    int ans = 0;
    for(int i =1; i <= n - 1; i ++) {
        int tmp[3];
        for(int j = 0;j < 2;j ++) {
            if(b.empty() || (!a.empty() && b.front() > a.front())) {
                tmp[j] =  a.front();
                a.pop();
            } else {
                tmp[j] = b.front();
                b.pop();
            }
        }
        ans += tmp[0] + tmp[1];
        b.push(tmp[0] + tmp[1]);
    }
    cout << ans;
} 

second method

use data structure:priority queue.its top is we want.Use it makes process easier.

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int> q;
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        q.push(-x);
    }
    int ans = 0;
    for(int i = 1; i <= n - 1;i ++) {
        int x1 = -q.top();
        q.pop();
        int x2 = -q.top();
        q.pop();
        ans += x1 + x2;
        q.push(-x1 - x2);
    } 
    cout << ans << endl;
}