P10385 [蓝桥杯 2024 省 B] 拔河

GXZJQ · 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;
}

提交记录