【做题笔记】P1090 合并果子

题目大意：给定 \(n\) 个数，每次可以任意选两个数 \(a_i,a_j\) 相加，把相加的结果作为一个新数继续执行此操作，直到只剩一个数为止。现要求使最后得出的这个数最小。

一个显然的贪心策略：每次选最小的两个数相加，得到一个新数，然后继续。但是，如果按照这样的思路，那么每次得到新数后这个序列的单调性就有可能会被破坏。

如何解决呢？很显然的一种方法，将新数加入序列后，再把这个序列排序。然而这样做似乎会超时。C++ STL 中提供了一种巧妙地解决方法：\(\mathtt{priority\_queue}\)。它地本质是建一个二叉堆，然后每当插入一个数，就维护这个二叉堆。那么显然，在这个题中，我们需要建一个小根堆，使较小的元素总是先被取出进行操作。

然后需要解决一个问题：

如何建立小根堆（使用\(\mathtt{priority\_queue}\))？

这样：priority_queue<int,vector<int>,greater<int> >q;。其中第一个 int 代表小根堆中存储的数据类型， vector<int> 代表存储的方式（vector 就是数组）， greater<int> 就是从小到大（即小根堆）。然后大根堆的话就是 priority_queue<int,vector<int>,less<int> >q;。

于是，做法就呼之欲出了：没读入一个数字，就插入小根堆中。然后，当元素个数大于等于 2 时循环，每次取出队首的两个元素相加，答案加上这个数字，再令新数入队即可。

请注意：这里为什么循环条件时元素个数大于等于 2而不是 队列不为空 呢？用兔队的一句话来回答：

参考代码：

#include <iostream>

#include <stdio.h>

#include <queue>

using namespace std;

int n,w;

priority_queue<int,vector<int>,greater<int> >q;

int main()

{

    long long ans=0;

    scanf("%d",&n);

    for(int i=1;i<=n;i++){scanf("%d",&w);q.push(w);}

    while(q.size()>=2)

    {

        int x=q.top();q.pop();

        int y=q.top();q.pop();

        x+=y;

        ans+=x;

        q.push(x);

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

【做题笔记】P1090 合并果子

最新文章

热门文章