题面描述

塔子哥想要最大化他的快乐值，针对每本书的满意值进行阅读安排。阅读每本书花费1单位时间，书的快乐值为已花费时间与满意值的乘积。给定满意值的字符串输入，例如"4,3,2"，表示书的满意值为4、3和2，塔子哥需要确定阅读顺序或选择不读某些书籍以获得最大的快乐值。输出为数字，代表最大快乐值之和。比如，输入"4,3,2"的输出为20，因为按照满意值的顺序阅读能够获得最大快乐值；而对于"-1,-4,-5"这样的输入，输出为0，因为不阅读任何书籍是最优选择。

思路：贪心

其实本质上就是最大化$\sum i\times a[i]$

首先，如果$a[i]\le 0$，则可以直接舍弃$a[i]$

对于正整数的情况，一定是优先把数值低的放在前面，数值高的放在后面，即直接对原数组进行升序排列即可。

题解思路

1. 舍弃低满意值书籍：对于任何满意值小于或等于0的书籍，阅读它们不会增加快乐值，因此我们可以直接舍弃这些书籍。

2. 优化阅读顺序：对于正的满意值，越高的满意值越应该在后面阅读，因为随着阅读时间的增加，乘积会增大。因此，我们将书籍的满意值进行升序排列，优先阅读满意值较低的书籍。

3. 计算最大快乐值：根据阅读顺序，我们可以通过一个循环计算每本书的贡献，累加得到最大快乐值。

时间复杂度

$O(nlogn)$

代码

C++

#include<bits/stdc++.h>
using namespace std;

int main() {
    string line;
    // 读取输入的满意值字符串
    getline(cin, line);
    stringstream ss(line);
    string token;
    vector<int> a;

    // 分割字符串并将每个满意值转为整数
    while (std::getline(ss, token, ',')) {
        int x = stoi(token);
        a.push_back(x);
    }

    // 对满意值进行升序排序
    sort(a.begin(), a.end());

    int ans = 0; // 用于存储最大快乐值
    int n = a.size();
    
    // 遍历数组，计算最大快乐值
    for (int i = 0; i < n; i++) {
        // 重置当前时间和当前快乐值
        int t = 1, now = 0;
        
        // 从第i本书开始计算
        for (int j = i; j < n; j++) {
            // 仅计算满意值大于0的书籍
            if (a[j] > 0) {
                now += t * a[j]; // 计算当前书籍的贡献
                t++; // 增加时间
                ans = max(ans, now); // 更新最大快乐值
            }
        }
    }

    cout << ans << endl; // 输出最大快乐值
    return 0;
}

python代码

# 从输入中读取书籍的满意值，并将其转换为整数列表
books = list(map(int, input().split(",")))

# 对满意值进行升序排序
books.sort()

# 计算书籍的数量
num_book = len(books)

# 初始化最大快乐值为0
ret = 0

# 第一部分：计算不舍弃任何书籍时的最大快乐值
for i in range(num_book):
    ret += books[i] * (i + 1)  # 计算当前书籍的贡献并累加到ret中

# 第二部分：尝试舍弃从第一本书到第num_book本书的每一本书
for i in range(num_book):
    books.pop(0)  # 从书籍列表中移除第一本书
    
    new_ret = 0  # 初始化新的快乐值
    # 计算剩余书籍的快乐值
    for j in range(num_book - i - 1):
        new_ret += books[j] * (j + 1)  # 计算每本剩余书籍的贡献并累加
    
    # 更新最大快乐值ret
    ret = max(ret, new_ret)

# 输出最终计算得到的最大快乐值
print(ret)

Java代码

import java.util.Arrays; // 导入数组操作相关的类
import java.util.Scanner; // 导入扫描器类以读取输入
import java.util.stream.IntStream; // 导入流处理类以进行数组的流操作

public class Main {
    @SuppressWarnings({ "resource" }) // 忽略未关闭的Scanner警告
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建Scanner对象以读取输入
        String[] strs = sc.nextLine().split(","); // 读取一行输入并以逗号分隔，存入字符串数组
        int[] arr = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray(); // 将字符串数组转换为整数数组
        
        Arrays.sort(arr); // 对整数数组进行升序排序
        
        int[] sum = new int[arr.length]; // 创建一个数组用于存储从当前索引到末尾的所有满意值的和
        int res = 0; // 初始化最大快乐值为0
        
        // 遍历数组，计算从每个位置到末尾的满意值和
        for (int i = 0; i < arr.length; i++) {
            // 计算从当前位置i到数组末尾的满意值和
            sum[i] = IntStream.of(Arrays.copyOfRange(arr, i, arr.length)).sum();
            
            // 如果当前的满意值和大于0，则将其加入结果
            if (sum[i] > 0) {
                res = res + sum[i]; // 更新结果
            }
        }
        
        // 输出最终计算得到的最大快乐值
        System.out.println(res);
    }
}