首页 > 分享 > 第十五届蓝桥杯省赛C/C++B组H题【拔河】题解（AC）

第十五届蓝桥杯省赛C/C++B组H题【拔河】题解（AC）

萌宠菠菠乐园
2024-09-21 20:27

请添加图片描述

题意分析

给定一个长度为 n n n 的数组，求两个子数组 [ l 1 , r 1 ] [l_1, r_1] [l1,r1]， [ l 2 , r 2 ] [l_2,r_2] [l2,r2] 的数组和差值最小是多少，其中 l 1 ≤ r 1 < l 2 ≤ r 2 l_1 leq r_1 < l_2 leq r_2 l1≤r1<l2≤r2。

O ( n 5 ) O(n^5) O(n5) 做法

枚举四个端点 O ( n 4 ) O(n^4) O(n4)，计算两个数组的和 O ( n ) O(n) O(n)，最终复杂度 O ( n 5 ) O(n^5) O(n5)。

O ( n 4 ) O(n^4) O(n4) 做法

做法同上，用前缀和优化数组求和的过程。

O ( n 3 ) O(n^3) O(n3) 做法枚举 r 1 , l 2 r_1, l_2 r1,l2，用双指针 i , j i, j i,j，分别从 r 1 , l 2 r_1, l_2 r1,l2，向左（右）扫描使得差值最小，详见代码。枚举 l 1 , r 2 l_1, r_2 l1,r2，用双指针 i , j i, j i,j，分别向中间扫描，取数组差值最小。 O ( n 2 l o g n ) O(n^2logn) O(n2logn) 做法

由于枚举三个点肯定会超时，所以只能枚举两个点，我们尝试枚举第一个区间 O ( n 2 ) O(n^2) O(n2)。

那么我们仅剩下 O ( l o g n ) O(logn) O(logn) 的复杂度，需要找出右区间中和左区间的和最相近的值，可以考虑使用 multiset（下文称为 S S S）。

一开始，我们将所有可能的右区间的区间和，都插入 S S S。

接下来，我们以 r 1 r_1 r1 递增进行枚举左区间，当 r 1 = k r_1 = k r1=k 时，我们在 S S S 中删除所有以 k k k 为左端点的区间的和。

细节处理：

可以通过前缀和优化区间求和过程。当左区间和为 k k k 时，我们可以使用 lower_bound，会返回 S S S 中的第一个 ≥ k geq k ≥k 的元素的迭代器（下文称为 p p p），当 p p p 等于 S S S.end() 时，表示不存在 ≥ k geq k ≥k 的元素，反之 ∗ p *p ∗p （类似于 C 语言中的指针）即为 S S S 中第一个 ≥ k geq k ≥k 的元素。另外，和 k k k 差值最小的数，除了 S S S 中 ≥ k geq k ≥k 的第一个元素以外，还可能是 S S S 中 < k < k <k 的最后一个元素，那么在一个有序列表中，上述两元素的下标差值应当为 1 1 1。所以我们还需要判断 p p p 的前一个位置是否存在元素。在 multiset 中删除一个和为 k k k 的区间的和时，不可以直接 erease，这样会导致 multiset 中的所有值为 k k k 的元素被删除。故我们可以用 find，找出一个值为 k k k 的元素的迭代器，将此传入 erease 删除，这样只会删除一个元素。 O ( n 3 ) O(n^3) O(n3) 做法

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <vector> using namespace std; typedef long long LL; const int N = 1e3 + 10; int n; int a[N]; int main() { cin >> n; for (int i = 1; i <= n; ++ i ) cin >> a[i]; LL res = 1e9; for (int i = 1; i <= n; ++ i ) for (int j = i + 1; j <= n; ++ j ) { int l = i - 1, r = j + 1; LL sl = a[i], sr = a[j]; res = min(res, abs(sr - sl)); while (l >= 1 && r <= n) { if (sl > sr) sr += a[r ++]; else sl += a[l --]; res = min(res, abs(sr - sl)); } while (l >= 1) { sl += a[l --]; res = min(res, abs(sr - sl)); } while (r <= n) { sr += a[r ++]; res = min(res, abs(sr - sl)); } } cout << res << endl; return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 O ( n 2 l o g n ) O(n^2logn) O(n2logn) 做法

#include <iostream> #include <cstring> #include <algorithm> #include <set> using namespace std; typedef long long LL; const int N = 1e3 + 10; int n; LL s[N]; multiset<LL> S; int main() { cin >> n; for (int i = 1; i <= n; ++ i ) cin >> s[i], s[i] += s[i - 1]; for (int i = 1; i <= n; ++ i ) for (int j = i; j <= n; ++ j ) S.insert(s[j] - s[i - 1]); LL res = 1e9; for (int i = 1; i < n; ++ i ) { for (int j = i; j <= n; ++ j ) { auto p = S.find(s[j] - s[i - 1]); S.erase(p); } for (int j = 1; j <= i; ++ j ) { auto k = s[i] - s[j - 1]; auto p = S.lower_bound(k); if (p != S.end()) res = min(res, abs(*p - k)); if (p != S.begin()) { p --; res = min(res, abs(*p - k)); } } } cout << res << endl; return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152

【在线测评】

在这里插入图片描述