给定 n, c 与 a _ 1, a _ 2, \cdots, a _ n，求 t = \max \limits _ {i = 1} ^ {k} a _ i + c \times (n - k) 的最小值。如果多个 t 相同且最小，输出 k 最小的一个。
其中 \max \limits _ {i = 1} ^ {k} a _ i 代表 a _ 1, a _ 2, \cdots, a _ k 中的最大值。特别的，如果 k = 0，则 \max \limits _ {i = 1} ^ {k} a _ i = 0。
题目分析
本题考察对循环结构的复杂运用。
我们可以注意到这样一个有趣的情况：
\begin{aligned}
& \max \limits _ {i = 1} ^ {k + 1} a _ i \\
= & \max \{ a _ 1, a _ 2, \cdots, a _ {k + 1}\} \\
= & \max(\max \{a _ 1, a _ 2, \cdots, a _ k\}, a _ {k + 1}) \\
= & \max((\max \limits _ {i + 1} ^ {k} a _ i), a _ {k + 1})
\end{aligned}
也就是，a 的前 k + 1 项的最大值可以通过将「前 k 项的最大值」与「第 k + 1 项」取最大值得到。
因此，我们可以使用一个变量 d 暂存这个最大值，在循环读入新数据 a _ i 时，进行对应的更新。
int d = 0;
for (int k = 1; k <= n; ++k) {
int x; // x 用于暂存 a 数据
cin >> x;
d = max(d, x);
}
在每次更新 d 后，我们可以非常容易地计算出此时的 t。最后，使用擂台法计算所有的 t 中的最小值即可。
在取最小值时，需要特殊处理「多个 t 相等」的情况，以及记录下对应的 k。
int d = 0;
int t = c * n; // k = 0，初始值
int ans = 0; // t 最小时的 k
for (int k = 1; k <= n; ++k) {
int x; // x 用于暂存 a 数据
cin >> x;
d = max(d, x);
if (d + c * (n - k) < t) {
t = d + c * (n - k);
ans = k;
}
}