【题解】P3918

P3918

题目

题目描述：

神犇航空开展了一项载客特技飞行业务。每次飞行长 $n$ 个单位时间，每个单位时间可以进行一项特技动作，可选的动作有 $k$ 种，每种动作有一个刺激程度 $c_i$。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间) ，若为第一次进行该动作，价值为 $0$。安排一种方案，使得总价值最大。

输入格式：

第一行，两个整数，$n$ 和 $k$，如上所述；

第二行，$k$ 个整数，表示 $k$ 种动作的 $c_i$ 值。

输出格式：

仅一行，一个整数，表示最大总价值。

数据范围与说明：

数据规模与约定

• 对于 $10\%$ 的测试数据，$n \le 20$，$k \le 3$。
• 对于 $100\%$ 的测试数据，$1 \le n \le 10^3$，$1 \le k \le 300$，$0 \le c_i \le 10^3$。

输入输出样例 #1

输入：

5 2
2 2

输出：

12

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> c(k);
    for (int i = 0; i < k; i++) {
        cin >> c[i];
    }
    sort(c.begin(), c.end(), greater<int>());
    int left = 0, right = n - 1;
    int ans = 0;
    for (int i = 0; i < k; i++) {
        if (left > right) break;
        ans += (right - left) * c[i];
        left++;
        right--;
    }
    cout << ans << endl;
    return 0;
}