P2234 [HNOI2002] 营业额统计 题解

· · 题解

从同学那学的神秘无数据结构无 STL 做法。题目链接。感觉多少有点好玩。

注意到值域很小，于是我们决定开一个布尔数组把所有出现的数标记为一。然后查询答案的时候，我们直接运行暴力即可。

我们考虑为什么这个暴力是对的。我们不难发现本质上是在干这么一件事情：维护数轴上的若干连续段，每次将一个连续段从中间裂成两半并取较小一半作为代价。考虑类似启发式合并的贡献分析方案，对于一个位置，它在一次操作中产生贡献当且仅当它位于被裂开的连续段中较小的那一部分。那么对于一个位置，它每一次贡献一定代表所处连续段长度至少除以二。换而言之，它的贡献至多为 O(\log A)。于是我们从而将该算法的复杂度分析为 O(n+A\log A)，可以较快通过。

代码和 set 的好写程度可能在伯仲之间。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 9;
int n, ans;
bool __vst[N << 1], *vst = __vst + N;
int calc(int x) {
  for (int i = 0; i <= N + x; ++i)
    if ((i < N - x && vst[x + i]) || vst[x - i]) return i;
  return x;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 0, a; i < n; ++i) cin >> a, ans += calc(a), vst[a] = true;
  return cout << ans << endl, 0;
}