自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:41，当前版本为作者最后更新于2024-11-12 19:37:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

思路 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;
}