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

一扶苏一 · 2024-04-30 03:33:32 · 题解

Description

给定一个序列，要求从中找到两个不相交的子段，使得两个子段元素和的差值尽可能小。

序列长度不超过 10^3。

Analysis

从大到小枚举 r_1。r_1 右侧的所有区间都是合法的第二个子段。用一个数据结构维护这些区间和。

再枚举 l_1。对于一个 [l_1, r_1] 的区间和 \mathrm {sum}，要在数据结构里找到离 \mathrm {sum} 最近的元素。

这是一个插入、lower_bound 问题，可以用 set 维护。

时间复杂度：每次右端点进行 r_1 \to r_1 - 1 移动时，把所有以 r_1 为右端点的区间加入 set。一共有 O(n^2) 个区间。插入的复杂度是 O(n^2 \log n)；对于一个 [l_1, r_1] 的区间，要在 set 里查询 lower_bound 找到不小于 \mathrm {sum} 的最小数，该位置前面的是小于 \mathrm {sum} 的最大数，一次查询是 O(\log n) 的，共 O(n^2) 次查询，复杂度也是 O(n^2 \log n)。于是总时间复杂度 O(n^2 \log n)。

Code

#include <bits/stdc++.h> 

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  using ll = long long;
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (auto &i : a) std::cin >> i;
  std::set<ll> s;
  ll ans = LONG_LONG_MAX;
  for (int r = n - 2; r >= 0; --r) {
    ll sum = 0;
    for (int l = r + 1; l < n; ++l) s.insert(sum += a[l]);
    sum = 0;
    for (int l = r; l >= 0; --l) {
      sum += a[l];
      auto p = s.lower_bound(sum);
      if (p != s.end()) {
        ans = std::min(ans, *p - sum);
      }
      if (p != s.begin()) {
        ans = std::min(ans, sum - *std::prev(p));
      }
    }
  }
  std::cout << ans  << '\n';
}