石子合并

题解

考点：思维/贪心

我选用的贪心策略是
（1）先合并最小的两个数，并从数据中删除
（2）将合并后的数插入，重复（1）直到序列中只有一个数

证明贪心的有效性
比如1 2 3 4 5
我选用最小的1和2，是为了让1*2，出现2
不想让1碰到比2更大的数，比如5，出现1*5，这样就有些浪费那个大的数
这样的代价，显然太大。我选用最小的两个，能够一步步合成更大的，进而使最终结构最大

代码

#include<bits/stdc++.h>
using namespace std;

//bool cmp(int a,int b)
//{
//    return a<b;
//    
//}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        //我选用优先队列模拟最小堆 ,注意这个优先级的设置方法，多了2个参数 
        priority_queue<int,vector<int>,greater<int> > solution;

        for(int i=0;i<n;++i)
        {
            int temp;
            scanf("%d",&temp);
            solution.push(temp); 
        }


                //数据量一般，用int不会溢出
        int sum=0;
        while(solution.size()>1)
        {
            int a=solution.top();
            solution.pop();
            int b=solution.top();
            solution.pop();
            sum+=(a*b);
            solution.push(a+b);
        }


        printf("%d\n",sum);
    }
    return 0;
}