51nod 1117(贪心+优先队列)

傷城~ 2022-07-26 01:29 193阅读 0赞

一位老木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN（1 <= L1,L2,…,LN <= 1000，且均为整数）个长度单位。我们认为切割时仅在整数点处切且没有木材损失。

木匠发现，每一次切割花费的体力与该木棒的长度成正比，不妨设切割长度为1的木棒花费1单位体力。例如：若N=3，L1 = 3,L2 = 4,L3 = 5，则木棒原长为12，木匠可以有多种切法，如：先将12切成3+9.，花费12体力，再将9切成4+5，花费9体力，一共花费21体力；还可以先将12切成4+8，花费12体力，再将8切成3+5，花费8体力，一共花费20体力。显然，后者比前者更省体力。

那么，木匠至少要花费多少体力才能完成切割任务呢？

题目的意思很明显，我们可以想到，这个题目和石子归并很相似，是石子归并的逆问题，但是结果是一样的。

题目要让我们分割，那么我们可以逆向思维去合并，结果是一样的。也就是说，怎么将n根木棒合并成一根并且花费最小。可以想到，每次都是两个木棒合并，并且花费是这两个木棒的价值和，那么就是和哈夫曼树一样了，将最小的放在最下面的节点上，他被计算的次数最多。

想到这里我们就可以解决这个问题了，一个优先队列，最小值优先，每次把前面的两个值拿出来然后将他们的和放进队列，时间复杂度为O(nlogn).

#include <map>
    #include <queue>
    #include <stack>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std ;
    #define mem(a) memset(a,0,sizeof(a))
    #define inf 100000005
    
    int const maxn = 50005;
    //优先队列，每次取出最上面的两个值，也就是最小的两个，知道队列里面没有值为止
    
    int main()
    {
        int n ;
        while(scanf("%d",&n)!=EOF)
        {
            priority_queue<int, vector<int>, greater<int> >q;//最小值优先
            while(!q.empty())q.pop();
            for(int i = 0 ; i < n ; i++)
            {
                int a ;
                scanf("%d",&a);
                q.push(a);
            }
    //        while(!q.empty())
    //        {
    //            cout<<q.top()<<" ";
    //            q.pop();
    //        }
    //        cout<<endl;
            long long ans = 0 ;
            while(!q.empty())
            {
                long long sum = 0 ;
                sum += q.top();
                q.pop();
                sum += q.top();
                q.pop();
                ans += sum ;
                if(q.empty())break;
                q.push(sum);
            }
            printf("%I64d\n",ans);
        }
        return 0 ;
    }