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

· · 题解

[语言月赛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。

视频题解

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