2 条题解
-
5
由题可知,本题让每次使用的两个纸条的长度加起来,直至纸条只剩一张。
我们采取贪心策略,每次取中两个最小长度的纸条,使之粘成一个纸条,每一次都是最小的选择,那么最后的结果也必然是最小。
若是采用sort进行排序,因为数据范围会超时。我们定义两个变量x,y为纸条的任意两个长度,遍历当前所有纸条,若其余长度大于x或y,则与之交换 ,使x, y成为最小值和次小值(也可以先sotr一遍,x, y为最小和次小)。之后保存两个数x,y之和,不断遍历寻找次小值或最小值,直至纸条数为一。
若还有不理解,欢迎qq来问我
这题还有一种比较简单的解法,就是使用优先队列,利用优先队列的特性,就能很轻松的写出来啦
-
0
int main() {int n; cin >> n; /* 创建最小堆名为pq。*/ priority_queue<int, vector<int>, greater<int> > pq; for (int i = 0; i < n; ++i) { int ai; cin >> ai; pq.push(ai); } long totalLength = 0; /*当仅剩一个纸条时结束。*/ while (pq.size() > 1) { int min1 = pq.top(); pq.pop(); int min2 = pq.top(); pq.pop(); int newLength = min1 + min2; totalLength += newLength; /*将生成的新纸条压入。*/ pq.push(newLength); } cout << totalLength << endl; return 0; }
- 1
信息
- ID
- 939
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 260
- 已通过
- 16
- 上传者