1 solutions
-
0
题面描述
塔子哥想要最大化他的快乐值,针对每本书的满意值进行阅读安排。阅读每本书花费1单位时间,书的快乐值为已花费时间与满意值的乘积。给定满意值的字符串输入,例如"4,3,2",表示书的满意值为4、3和2,塔子哥需要确定阅读顺序或选择不读某些书籍以获得最大的快乐值。输出为数字,代表最大快乐值之和。比如,输入"4,3,2"的输出为20,因为按照满意值的顺序阅读能够获得最大快乐值;而对于"-1,-4,-5"这样的输入,输出为0,因为不阅读任何书籍是最优选择。
思路:贪心
其实本质上就是最大化
首先,如果,则可以直接舍弃
对于正整数的情况,一定是优先把数值低的放在前面,数值高的放在后面,即直接对原数组进行升序排列即可。
题解思路
-
舍弃低满意值书籍:对于任何满意值小于或等于0的书籍,阅读它们不会增加快乐值,因此我们可以直接舍弃这些书籍。
-
优化阅读顺序:对于正的满意值,越高的满意值越应该在后面阅读,因为随着阅读时间的增加,乘积会增大。因此,我们将书籍的满意值进行升序排列,优先阅读满意值较低的书籍。
-
计算最大快乐值:根据阅读顺序,我们可以通过一个循环计算每本书的贡献,累加得到最大快乐值。
时间复杂度
代码
C++
python代码
Java代码
-
- 1
Information
- ID
- 64
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 86
- Accepted
- 36
- Uploaded By