/ Vijos / 讨论 / 问答 /

站外题求助

本人蒟蒻一个,请各位大佬帮忙看看。
不是贪心

围栏修复

描述

有一个农夫要把一个木板锯成N(1<=N<=20000)块给定长度的小木板,每次锯都要收取一定费用,这个费用就是当前锯的这个木版的长度。
给定各个要求的小木板的长度Li(1<=Li<=50000),及小木板的个数N,求最小费用。

输入

第1行包含整数N,表示木板的数量。
接下来N行,每行一个所需木板的长度Li

输出

一个正整数,表示锯木板的最小花费

样例输入

3
8
5
8

样例输出

34

1 条评论

  • @ 2024-12-15 12:01:33

    此贴结,以下AC代码

    
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;
        cin >> n;
        priority_queue<int, vector<long long>, greater<int>> pq;
        for (int i = 0; i < n; i++) {
            long long num;
            cin >> num;
            pq.push(num);
        }
        long long cost = 0;
        while (pq.size()>1) {
            long long first = pq.top();
            pq.pop();
            long long second = pq.top();
            pq.pop();
            long long sum = first + second;
            cost+=sum;
            pq.push(sum);
        }
        cout << cost << endl;
        return 0;
    }
    
    
  • 1