自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:15:14，当前版本为作者最后更新于2023-08-12 10:23:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Source & Knowledge

2023 年 8 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定 $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;
    }
}

视频讲解

视频题解后续将会上传。