B4038 [GESP202409 三级] 平衡序列

chen_zhe · 2024-11-12 19:37:42 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

:::align{center} :::

思路 1（无法通过本题）

题目问，是否存在一个正整数 i，使得序列第 1 到第 i 个数字的总和等于第 i+1 到第 n 个数字的总和。

因此，使用一重循环枚举 i，在循环内部使用第二层循环，统计序列第 1\sim i 个数字之和，以及第 (i+1) \sim n 个数字之和，判断是否相等。

这样做的结果虽然是正确的，但是无法通过本题。这是因为，循环枚举的时间复杂度是 O(n^2)，而测试数据有 t 组，合计为 O(tn^2)，在 t=100，n=10^4 时会超时。

思路 2（可以通过本题）

把序列第 1\sim i 个数字的总和，与第 (i+1) \sim n 个数字的总和相等，相当于把原来序列的总和分成两个相等的一半。例如说：

2 3 1 4

在这个例子中，序列的总和是 2+3+1+4=10，而 2+3=1+4=5，相当于第 1,2 个数字的总和，恰好等于序列总和的一半。

因此，在读入序列 a 的时候，记录下序列 a 的总和。接着还是枚举正整数 i，但是在枚举的时候记录下 a_1,a_2,\dots,a_i 的总和，如果存在一个 i，使得总和能够恰好是序列总和的一半，那么说明序列是平衡的。

这样的做法，对于每组测试数据，只有一层循环进行处理，总的时间复杂度是 O(tn)，在 t=100，n=10^4 时可以通过本题。

需要注意，本题有多组测试数据，因此在处理每一组测试数据之前，记录总和、标记答案的相关变量都需要初始化，以免造成意料之外的情况。

参考代码（只保留关键部分）：

//需要初始化变量 sum, sum2, flag
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum += a[i];
}
for (int i = 1; i <= n; i++) {
    sum2 += a[i];
    if (sum2 * 2 == sum)
        flag = true;
}