2 条题解
-
5
由题可知,本题让每次使用的两个纸条的长度加起来,直至纸条只剩一张。
我们采取贪心策略,每次取中两个最小长度的纸条,使之粘成一个纸条,每一次都是最小的选择,那么最后的结果也必然是最小。
若是采用sort进行排序,因为数据范围会超时。我们定义两个变量x,y为纸条的任意两个长度,遍历当前所有纸条,若其余长度大于x或y,则与之交换 ,使x, y成为最小值和次小值(也可以先sotr一遍,x, y为最小和次小)。之后保存两个数x,y之和,不断遍历寻找次小值或最小值,直至纸条数为一。
若还有不理解,欢迎qq来问我
这题还有一种比较简单的解法,就是使用优先队列,利用优先队列的特性,就能很轻松的写出来啦
信息
- ID
- 939
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 260
- 已通过
- 16
- 上传者