自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:14:38，当前版本为作者最后更新于2018-05-20 15:20:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[语言月赛202303] Milk Sales S 题解

Source & Knowledge

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

本题考察循环结构。

文字题解

题目大意

给定两个数列 $a, b$，要求找到最小的 $x$，满足 $a_1 + a_2 + \dots + a_x < b_1 + b_2 + \dots b_x$。

解析

算法一

一个简单的做法是从小到大枚举 $x$，然后每次计算 $sa = a_1 + a_2 + \dots + a_x$ 和 $sb = b_1 + b_2 + \dots + b_x$，找到最小的 $x$ 并比较。

for (int x = 1; x <= n; ++x) {
  long long sa = 0, sb = 0;
  for (int i = 1; i <= x; ++i) {
    sa += a[i]; sb += b[i];
  }
  if (sa < sb) {
    ans = x; break;
  }
}

这一做法使用了一个循环嵌套。外层循环大小为 $n$，内层循环大小的上界也是 $n$。

更具体的分析，循环的执行次数是 $1 + 2 + 3 + \dots + n = \frac{n + n^2}{2}$。也就是总的运算量大约有 $n^2$ 次。可以通过 $n \leq 5 \times 10^3$ 的数据。当 $n = 10^5$ 时，$n^2$ 达到了 $10^{10}$ 级别。计算机一秒大约只能执行 $10^8$ 次运算，所以无法通过本题。

算法二

观察算法一的代码，可以发现 $sa$ 和 $sb$ 事实上不需要每次都重新计算。

具体来说，假设上次循环已经求出了 $sa' = a_1 + a_2 + \dots + a_{x - 1}$，那么本次要求的 $sa = a_1 + a_2 + \dots + a_{x} = sa' + a_{x}$。只需要用两个变量分别维护 $sa$ 和 $sb$，当 $x$ 增加时，把它们分别加上 $a_x$ 和 $b_x$ 并作比较即可。

long long sa = 0, sb = 0;
for (x = 1; x <= n; ++x) {
  sa += a[x]; sb += b[x];
  if (sa < sb) {
    ans = x; break;
  }
}

这份代码只用了一个长度为 $n$ 的循环，运算量在 $10^5$ 数量级，可以通过本题。

需要注意的是，$sa$ 和 $sb$ 的最大值可能达到 $10^5 \times 10^9 = 10^{14}$。因此需要开 long long。

视频题解

完整代码请在视频中观看。