题目描述

  塔子哥是个爱学习的孩子，并且喜好读书，并且更喜欢读好书，在某一天他要读n本书，读每一本书都要花费1单位时间，并且塔子哥对每一本书有一个满意值，同时读完每一本书塔子哥都会收获一定的快乐值，现在塔子哥想知道要按照怎样的顺序读书读哪些书能使他收获的快乐值总和最大

  每本书籍的快乐值为读这本书和之前所有书所花费的时间乘以对这本书的满意值，可按照任意顺序读书，也可以放弃读某些书。

设书的总数为n，书的满意值为m

$1\leq n\leq 500$

$-1000\leq m\leq 1000$

输入描述

输入为字符串，字符串内容为代表每本书籍的满意值，例如输入为"4,3,2"，表示有3本书，满意值分别是4、3和2

输出描述

输出为数字，代表最大的快乐值之和

样例

输入1

4,3,2

输出1

20

说明

按照原来顺序相反的时间阅读书籍(2 * 1 +3 * 2+4 * 3=20)，满意值越高的书籍越后面读可以获得最大的快乐值。

输入2

-1,-4,-5

输出2

0

说明

这些书籍满意值都很低，所以不阅读任何书籍可以获得最大的快乐值 。

输入3

-1,-8,0,5,-9

输出3

14

说明

去掉第二个和最后一本书籍，最大的快乐时间系数和为(-1 * 1+0 * 2+5 * 3=14)每书籍都需要花费1单位时间来阅读 。

题面描述

塔子哥想要最大化他的快乐值，针对每本书的满意值进行阅读安排。阅读每本书花费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);
    }
}