- 问答
- 2024-12-07 21:40:40 @
本人蒟蒻一个,请各位大佬帮忙看看。
不是贪心
围栏修复
描述
有一个农夫要把一个木板锯成N(1<=N<=20000)块给定长度的小木板,每次锯都要收取一定费用,这个费用就是当前锯的这个木版的长度。
给定各个要求的小木板的长度Li(1<=Li<=50000),及小木板的个数N,求最小费用。
输入
第1行包含整数N,表示木板的数量。
接下来N行,每行一个所需木板的长度Li
输出
一个正整数,表示锯木板的最小花费
样例输入
3
8
5
8
样例输出
34
1 条评论
-
ssjs2023scy LV 4 @ 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