[HNOI2002] 营业额统计

题意

第一天波动值为当天营业额。此后每天的波动值是它与此前任意一天营业额的最小绝对差，求所有波动值之和。

思路

在一组有序数中，离新值最近的旧值只可能是它的前驱或后继。问题变成动态维护已出现营业额，并查询前后两个值。

Python 标准库没有平衡树。因为所有营业额已在输入中，可以先 sorted(set(values)) 离散化，再用 Fenwick 树记录哪些不同值已经出现。

对一个首次出现的值：

前缀和得到比它小的已出现值数量 less；
Fenwick 的 kth(less) 找前驱，kth(less+1) 找后继；
取两个差值的较小者；
把当前排名加入树。

重复营业额的波动为零，不必重复加入只记录“是否出现”的树。

Python 知识

sorted(set(values)) 同时完成去重和排序。
字典推导式建立“原值到离散排名”的映射。
seen 集合用平均 $O(1)$ 判断重复值。
index & -index 是 Fenwick 树的 lowbit；kth 用二进制倍增寻找第 k 个已出现排名。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：排序与规范化。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：集合与字典。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
values = data[1:1 + n]
ordered = sorted(set(values))
rank = {value: index + 1 for index, value in enumerate(ordered)}
tree = [0] * (len(ordered) + 1)


def add(index):
    while index < len(tree):
        tree[index] += 1
        index += index & -index


def prefix_sum(index):
    total = 0
    while index:
        total += tree[index]
        index -= index & -index
    return total


def kth(order):
    index = 0
    step = 1 << (len(tree).bit_length() - 1)
    while step:
        nxt = index + step
        if nxt < len(tree) and tree[nxt] < order:
            index = nxt
            order -= tree[nxt]
        step >>= 1
    return index + 1


answer = values[0]
seen = {values[0]}
add(rank[values[0]])

for value in values[1:]:
    if value in seen:
        continue
    index = rank[value]
    less = prefix_sum(index - 1)
    total = len(seen)
    differences = []
    if less:
        differences.append(value - ordered[kth(less) - 1])
    if less < total:
        differences.append(ordered[kth(less + 1) - 1] - value)
    answer += min(differences)
    seen.add(value)
    add(index)

print(answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * P2234 [HNOI2002] 营业额统计
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 33000;
int a[MAXN];  // 存所有营业额
int n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    // 第一天波动值就是当天营业额本身
    long long ans = a[1];
    // 对每天 i，在前 i-1 天中找与 a[i] 差值最小的那天
    for (int i = 2; i <= n; ++i) {
        int min_diff = abs(a[i] - a[1]);
        for (int j = 2; j < i; ++j) {
            int diff = abs(a[i] - a[j]);
            if (diff < min_diff) min_diff = diff;
        }
        ans += min_diff;
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

离散化为 $O(n\log n)$ ，每个不同值查询和插入为 $O(\log n)$ ；总时间 $O(n\log n)$ ，空间 $O(n)$ 。

总结

动态最近值只需前驱和后继。缺少标准平衡树时，“已知全部值 + 坐标压缩 + Fenwick 第 k 小”是可靠的 Python 替代方案。

[HNOI2002] 营业额统计

目录

题意

思路

Python 知识

代码

复杂度

总结