自动搬运

查看原文

来自洛谷，原作者为

	GXZJQ AFO||十年竞赛一场空 不开 long long 见祖宗

搬运于2025-08-24 22:57:53，当前版本为作者最后更新于2024-04-30 14:36:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10385 [蓝桥杯 2024 省 B] 拔河 题解

• 更新于 $2024$ 年 $5$ 月 $10$ 日：修改了第二份代码中的小错误，感谢 MyNameIsikun 的指正和 hack 数据。

• 更新于 $2024$ 年 $5$ 月 $12$ 日：修改了题目链接的指向，感谢 wzj0829 的提醒。

题目链接

题目大意

给定一个长度为 $n$ 的序列，求出两个子序列 $[l_1,r_1]$ 和 $[l_2,r_2]$ 中数字和的差值的最小值，保证 $l_1 \le r_1\le l_2 \le r_2$。

题目分析

思路一：暴力 $\mathcal {O}(n^5)$

使用循环，暴力枚举区间的左右端点并进行求和，最后比较差值。由于枚举端点的时间复杂度为 $\mathcal {O}(n^4)$，求和的时间复杂度为 $\mathcal {O}(n)$，所以最终时间复杂度为 $\mathcal {O}(n^5)$，无法通过本题。

思路二：暴力+前缀和 $\mathcal {O}(n^4)$

同思路一，暴力枚举区间的左右端点并进行求和，最后比较差值。但我们使用前缀和维护序列和的时候可以优化掉暴力求和的 $\mathcal {O}(n)$，所以最终时间复杂度为 $\mathcal {O}(n^4)$，无法通过本题。

思路三：双指针 $\mathcal {O}(n^3)$

• 枚举 $r_1,l_2$，定义双指针 $i,j$，分别从 $r_1$ 和 $l_2$，分别从左边和右边扫描整个序列；

• 枚举 $l_1,r_2$，定义双指针 $i,j$，向中间扫描整个序列。

使用双指针的总体复杂度为 $\mathcal {O}(n^3)$，理论上可以通过，但还不够优秀。

思路四：枚举单个区间 $\mathcal {O}(n^2 \log n)$

双指针算法仅仅是理论上可以通过，但可能会出现一些小的情况造成超时。这时我们就要用一种时间复杂度更为优秀的算法。

我们尝试只用 $\mathcal {O}(n^2)$ 枚举第一个区间 $[l_1,r_1]$，然后回归题目本身，它要求数字和差值尽可能小，所以要在右区间中找到和左区间的和最相近的值，不妨使用一个 multiset 进行维护，记其为 $S$。

开始的时候，我们把所有可能的右区间的和都加入 $S$ 中去，接下来用 $r_1$ 枚举左区间，当 $r_1=k$ 时，在 $S$ 中删除以 $k$ 为左端点的区间和。

细节和优化

• 用前缀和维护整个序列的数字和；

• 使用 lower_bound 二分查找第一个大于等于 $k$ 的位置；

• 注意 multiset 的维护，不可以直接使用 erase，而是要对其传入一个值为 $k$ 的元素的迭代器，有指向性地删除。

参考代码

双指针 $\mathcal {O}(n^3)$

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, a[maxn];
int ans = INT_MAX;
int minnum(int a, long long b) {
	return a > b ? b : a;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) {
			int l = i - 1, r = j + 1;
			long long suml = a[i], sumr = a[j];
			ans = minnum(ans, abs(suml - sumr));
			while (l >= 1 && r <= n) {
				if (suml > sumr) sumr += a[r++];
				else suml += a[l--];
				ans = minnum(ans, abs(suml - sumr));
			}
			while (l >= 1) {
				suml += a[l--];
				ans = minnum(ans, abs(suml - sumr));
			}
			while (r <= n) {
				sumr += a[r++];
				ans = minnum(ans, abs(suml - sumr));
			}
		}
	cout << ans << endl;
	return 0;
}

提交记录

枚举单个区间 $\mathcal {O}(n^2 \log n)$

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n;
long long a[maxn], ans = 1e9;
multiset<long long> S;
long long minnum(long long a, long long b) {
	return a > b ? b : a;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], a[i] = a[i - 1] + a[i];//前缀和维护
	for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) S.insert(a[j] - a[i - 1]);//全部插入
	for (int i = 1; i < n; i++) {
		for (int j = i; j <= n; j++) {
			auto p = S.find(a[j] - a[i - 1]);
			S.erase(p);//删除
		}
		for (int j = 1; j <= i; j++) {
			auto k = a[i] - a[j - 1];
			auto p = S.lower_bound(k);
			if (p != S.end()) ans = minnum(ans, abs(*p - k));
			if (p != S.begin()) p --, ans = minnum(ans, abs(*p - k));
		}
	}
	cout << ans;
	return 0;
}

提交记录