P1090. 合并果子

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 226 阅读时长 ≈ 1 分钟

考点

  • 贪心
  • 堆
  • 优先队列

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int v_;
    Node(int v = 0) : v_(v) {}
};

bool operator<(const Node &a, const Node &b)
{
    return a.v_ > b.v_;
}

priority_queue<Node> q;

int main()
{
    int n, in;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> in;
        q.emplace(Node(in));
    }
    int a, b, t, ans = 0;
    while (q.size() > 1)
    {
        a = q.top().v_, q.pop();
        b = q.top().v_, q.pop();
        ans += (t = a + b);
        q.emplace(Node(t));
    }
    cout << ans;
    return 0;
}

思路

哈夫曼树的模板题

根据本题要求，能做到插入和弹出都做到有序的，只有堆（或者叫优先队列）

C++的priority_queue排序实现略有反人类，默认比较仍是<，但却是大根堆....（降序排列，正常都是升序排列）

所以需要新建一个结构体，并重载<，内部的排序规则反着来就行

我们要求升序，但是在这里就需要写成降序的样子

1
2
3
4
bool operator<(const Node &a, const Node &b)
{
    return a.v_ > b.v_;
}