小粉兔的期末考试压力值最小化 - 算法与代码实现

小粉兔在 T 大学就读。在 1 月 54 日，T 大学开始了一学期一度的期末考试环节。

小粉兔本学期有 'n' 科考试，按照时间先后顺序依次被标号为 1, 2, ⋯, n。每一科考试都具有一个难度系数 'a_i' 。

如果准备这么多考试，小粉兔很可能会压力激增。因此，他想要仅准备并参与一部分考试，而将剩余的科目申请缓考。具体的，他可以选择准备前任意科考试（可以是 0 门，可以是 'n' 门），而剩余的科目不做准备。

但是，缓考的考试在下学期仍然需要参加，所以小粉兔会对他的决策做一个评估。他会使用'压力值'去完成这一评估过程。

具体的，我们设小粉兔选择参加前 'k' 科考试（0≤k≤n）。给定一个压力系数 'c'，此时他的压力值 't' 的计算方式如下：

't = max_i=1^k a_i +c×(n−k)'

其中 max_i=1^k a_i 代表 a₁, a₂, ⋯, a_k 中的最大值。特别的，如果 k=0，则 max_i=1^k a_i =0。

现在，小粉兔知道了考试的科数 'n' 和每门考试的难度系数 a₁, a₂, ⋯, a_n ，请你帮他计算出'压力值'最小时需要准备的考试科目数量。

输入格式

输入共两行。

第一行为两个整数 'n, c'，分别代表考试的科目数和压力系数。 第二行为 'n' 个整数 a₁, a₂, ⋯, a_n ，代表每门考试的难度系数。

输出格式

输出共一行两个整数，依次代表小粉兔'压力值'最小时需要准备的考试科目数量 'k' 和对应的最小'压力值'。如果有多个 'k' 对应的'压力值'相同且最小，请在相应位置输出其中最小的一个。

输入输出样例

输入 #1

3 2
2 3 5

输出 #1

2 5

输入 #2

10 3
6 4 5 5 6 2 2 4 19 9

输出 #2

8 12

输入 #3

3 2
7 2 5

输出 #3

0 6

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int k = 0;
    int minPressure = INT_MAX;
    for (int i = 0; i <= n; i++) {
        int maxDifficulty = 0;
        for (int j = 0; j < i; j++) {
            maxDifficulty = max(maxDifficulty, a[j]);
        }
        int pressure = maxDifficulty + c * (n - i);
        if (pressure < minPressure) {
            minPressure = pressure;
            k = i;
        }
    }
    
    cout << k << ' ' << minPressure << endl;
    
    return 0;
}

算法思路

首先读入考试的科目数 n 和压力系数 c，以及每门考试的难度系数 a1, a2, ..., an。

然后，遍历所有可能的准备科目数量 k，从 0 到 n。

对于每一个 k，计算准备前 k 门考试的最大难度系数 maxDifficulty，以及对应的压力值 pressure。

如果当前的压力值 pressure 小于之前的最小压力值 minPressure，更新 minPressure 和对应的准备科目数量 k。

最后输出准备科目数量 k 和最小压力值 minPressure。