洛谷:P2234 [HNOI2002]营业额统计

(Updated: )
OI
views
Word count: 547 (~2 mins to read) Last updated:

原题地址：https://www.luogu.org/problemnew/show/P2234

题目简述

给定一个序列，对于每一个数都要查询：序列中在这个数前与这个数最接近的数是什么？然后将最接近的数字与这个数字的差累加。（序列第一个数字直接加自己）

思路

查询在这个数之前与这个数最接近的数，我们很容易想到用二叉搜索树（BST）来做。
虽然数据略水暴力排序每次查询从一个数往左右找也能过。
每次插入一个数字，然后查询，我用Treap实现（还是弱化版的，只有插入查询）。
Treap的核心其实就是打乱顺序插入防止被卡（粗糙理解）。具体实现方法不难，请百度。（我之后会写一篇专门介绍下各种BST的。）
PS：Treap树完整版之后写。这题用STL的vector也行，vector理论每次插入渐进时间复杂度是O(n)但是听说实际是对数级别的？

代码

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
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
inline int randad(){
    static int seed=114; //seed可以随便取
    return seed=int(seed*48271LL%2147483647);//48271使得其有完全周期，即2147483647内取遍不重复 
}
struct Treap {
    int key,pri,son[2];
}T[33333];
int cnt=1,rt=0;
void rotate(int p,int &rt)
{
    int y=T[rt].son[p];
    T[rt].son[p]=T[y].son[!p];
    T[y].son[!p]=rt;
    rt=y;
}
void ins(int key,int &rt)
{
    if(rt==0)
    	T[rt=cnt++] = (Treap){key,randad()};
    else
    {
        int p=key>T[rt].key;
        ins(key,T[rt].son[p]);
        if(T[T[rt].son[p]].pri>T[rt].pri)
        	rotate(p,rt);   
    }
}
int nowMin(int key,int rt)//查询现在最接近key的数
{
    if(rt==0) return 666666666;
    int res=abs(key-T[rt].key);
    if(key>T[rt].key) res=min(res,nowMin(key,T[rt].son[1]));
    else if(key<T[rt].key) res=min(res,nowMin(key,T[rt].son[0]));
    return res;
}
int n,tot=0;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        int num;
        scanf("%d",&num);
        if (i==1) tot+=num;
        else tot+=nowMin(num,rt);//rt是当前根
        ins(num,rt);
    }
    printf("%d",tot);
    return 0;
}