自动搬运

查看原文

来自洛谷，原作者为

	zcq_qwq 仅回关灰名以上用户 || 坐标CQ || 求壶关QWQ || 太矮，被人群淹没了

搬运于2025-08-24 22:45:36，当前版本为作者最后更新于2025-05-26 10:59:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

说在前面

感觉想了三天才做出来的自己跟个人一样……

小建议：把思路写在代码下面是一种非常好的习惯，容易梳理思路，记得多提问。具体怎么做看后面。

题目分析

接下来，我将带领你一步一步，从根开始，找到解题思路。

首先，题目要求改变 $a _ i$ 的值，找到两个不同的连续子序列，它们的和相等。求 $\min \{ |\Delta a _ i|\}$。

其中，$|$ 是绝对值的意思，就是把满足 $a < 0$ 的数变成 $-a$。$\Delta x$ 指的是 $x$ 的改变量，也就是现在的 $x$ 减去原来的 $x$。

现在思考：这两个序列有什么特点？

题目中提到：初始状态下没有两个和相等的连续子序列。所以，如果序列中不包含 $a_i$，那么显然是不行的。因为如果这两个序列与 $a _ i$ 无关，则 $a _ i$ 的变化与对两个序列的和没有影响。那么现在我们得出：两个序列中至少包含 $1$ 个 $a _ i$。

包含两个行不行？也不行。因为如果两个序列都与 $a _ i$ 有关，那么两个序列同时加上或减去一个相同的数，大小关系不变。

得出结论：只有一个序列包含 $a _ i$。

则问题转化为：找到一个包含 $a _ i$ 的序列和一个不包含 $a _ i$ 的序列，他们差值的绝对值最小。

那么我们先求出所有子序列的和：

for (int i = 1; i <= n; i++) { // 前缀和
    s[i] = s[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        sum[i][j] = s[j] - s[i - 1];
    }
}

然后，统计答案。但是直接做时间复杂度大的逆天，光枚举区间就得六重循环。所以，考虑优化。

先把区间信息存进结构体数组：

struct arr {
    int l, r, sum;
} b[N];
...
int cnt = 0;
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        b[++cnt] = {i, j, s[j] - s[i - 1]};
    }
}

随后，我们想一想：最小差值可能出现在什么地方？

是不是很简单？排序后数组相邻的两个数。

所以，按 $sum$ 由小到大排序。

struct arr {
    ...
    bool operator < (const arr & x) const {
        return sum < x.sum;
    }
} b[N];
...
sort(b + 1, b + cnt + 1); // 如果不重载小于号要手写比较函数。

那么，枚举相邻的两个序列就行了。

这里给出证明：

假设最小产生在 $b _ i$ 和 $b _ {i + 2}$ 之间（不相邻）。那么应有：

$$b _ {i + 2} - b _ i < b _ {i + 1} - b _ i$$

即

$$b _ {i + 2} < b _ {i + 1}$$

这与 $b _ {i + 1} < b _ {i + 2}$ 矛盾！

所以假设不成立。

那么我们如何得知区间是否包含 $a _ i$ 呢？

这时候，我们在结构体里存的 $l$ 和 $r$ 就有用了。

不用去枚举 $l$ 到 $r$，只需要判断 $l \le i \le r$ 就行了。还是那句话：初始状态下没有两个连续子区间的和相等。

对于每一个 $a _ i$，扫描整个序列数组，如果一个序列和跟它相邻的序列一共只包含一个 $a _ i$，那么将它们的和相减，与答案取最小值。这一轮结束后输出答案。

至此，分析结束，时间复杂度 $O(n ^ 3)$，三次方是因为子序列个数有 $\frac{n \dot (n + 1)}{2}$ 个，乘上枚举 $a _ i$ 的 $O(n)$，算下来是 $\Theta (\frac{n ^ 2 \dot (n + 1)}{2})$，差不多 $O (n ^ 3)$。

注意事项

$$ans = \min \{ sum _ {b _ {i + 1}} - sum _ {b _ {i}} \} $$

这里不用加绝对值，因为是从小到大排序。

完整代码（最下面就是思路）

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 500 + 5;

int a[N], s[N];

struct arr {
	int l, r, sum;
	
	bool operator < (const arr & x) const {
		return sum < x.sum;
	}
} b[N * N];

int n;

bool check(int l, int r, int x) {
	return l <= x && x <= r;
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			b[++cnt] = {i, j, s[j] - s[i - 1]};
		}
	}
	sort(b + 1, b + cnt + 1);
	for (int i = 1; i <= n; i++) {
		int ans = 0x3f3f3f3f3f3f3f3f;
		for (int j = 1; j < cnt; j++) {
			if (check(b[j].l, b[j].r, i) && !check(b[j + 1].l, b[j + 1].r, i) || !check(b[j].l, b[j].r, i) && check(b[j + 1].l, b[j + 1].r, i)) {
				ans = min(ans, b[j + 1].sum - b[j].sum);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

/*
题目说要求改变 ai 的值，使得有两个不同的连续子序列相等。
那么，这两个子序列有什么特点？
题目说一开始没有两个不同子序列的和相等，说明 ai 的值对序列有影响。
所以两个序列中至少有一个包含 ai？
不对，应该是只有一个。因为两个序列同时加上相同的值，大小关系不变。
所以要求包含 ai 的序列 和 不包含 ai 的序列 的 最小差值。
先求出所有子序列的和：
for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
		for (int k = i; k <= j; k++) {
			sum[i][j] += a[k];
		}
	}
}
时间复杂度是 O(n ^ 3)，会不会炸？
显然不会。题目指出 1 <= N <= 500。
随后来比较。但是直接比较显然会超时。
那我们如何高效的找到不含 ai 和 含 ai 的序列呢？
把序列信息存入结构体中。
struct arr {
	int l, r, sum;
} b[N];
.....
int cnt = 0;
for (int i .....n; i++) 
	for (int j .....n; j++) {
		b[++cnt] = {i, j, sum[i][j]};
	}
}
哦，不用这么麻烦，可以先预处理前缀和。
for (int i = 1; i <= n; i++) {
	sum[i] = sum[i - 1] + a[i];
}
for (i......) 
	for (j.......)
		b[++cnt] = {i, j, sum[i] - sum[j - 1]};
现在怎么做？
可以排个序，这样相邻的差值一定是最小的。
假设 ai 的存在情况如下：

0 1 0 0 1 1 0 0 
怎么找？
看起来只要找相邻的就可以了。
每次枚举相邻两个区间。看如果一边有 ai 一边没有 ai，就计算答案。
如何证明？
可以知道，排序后差值最小一定产生在相邻两个数。假设不产生在 b(i + 1)，产生在 b(i + 2)：
则我们可知
bi < b(i + 1) < b(i + 2);
b(i + 1) - bi < b(i + 2);
证毕。
但怎么判断有没有ai这个数呢？
原始思路：枚举 l ~ r 看有没有 ai。
但是题目说了没有相同的子序列，也就是数互不相同！！！
所以 一旦 l <= i <= r，就说明他在这个区间内！！！
所以判断相邻两段区间是否一个包含一个不包含，如果是则 ans = min(ans, b[i + 1].sum - b[i].sum)；
输出答案即可。
至此，思路完全打开。
*/

说在后面

若思路、代码讲解有误，欢迎提出！