APIO/CTSC 2007数据备份

发表于 更新于 分类于 阅读次数：

这两个题思路是一样的，都要用到优先队列和链表 [APIO/CTSC 2007]数据备份 种树 就以数据备份这个题为例： 首先我们可以知道，要取得最短配对方案，一定是相邻的楼相连，并且每对之间有空隙 可以把所有两个楼之间空隙放进数组中处理，即在数组中不能相邻取数 对于一个最小的空隙，在最优方案中它要么被选取，要么两边的空隙被选取。这是因为如果上述都不满足的话，任意少取一个空隙换成最小空隙，都可以让答案更小 所以，我们使用一个优先队列和一个链表：每次取出最小值和两边的数$d[i],d[i-1],d[i+1]$，在答案中加上$d[i]$，然后将$d[i-1]+d[i+1]-d[i]$放在原$d[i]$的位置并更新链表 如果之后使用到了这个新值，即抛弃了使用$d[i]$，选取了$d[i-1]+d[i+1]$，满足最优方案 注意边界，设成$INF$ PS：我自己都嫌弃自己代码丑……

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
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int a = 1, b = 0; char c = getchar();
    while (c < '0'  c > '9') {
        if (c == '-') a = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        b = b * 10 + c - '0';
        c = getchar();
    }
    return a * b;
}

const int MAXN = 500000 + 233;
int L[MAXN], R[MAXN];
int N, K;
long long ans;

int tree[MAXN];
int dis[MAXN];

typedef pair<int, int> Pair;
priority_queue<Pair, vector<Pair>, greater<Pair> > que;

bool del[MAXN];

int main()
{
    N = read(); K = read();
    for (int i = 1; i <= N; ++i) {
        dis[i] = read();
    }
    for (int i = 2; i <= N; ++i) {
        tree[i] = dis[i] - dis[i - 1];
        que.push(make_pair(tree[i], i));
        L[i] = i - 1;
        R[i] = i + 1;
    }
    tree[0] = tree[1] = tree[N + 1] = tree[N + 2] = 1 << 30;
    L[N + 1] = N;
    R[0] = 1;
    while (K--) {
        int v = que.top().first, p = que.top().second;
        que.pop();
        if (del[p]) {
            ++K;
            continue;
        }
        if (v < 0) {
            break;
        }
        ans += v;
        del[L[p]] = del[R[p]] = true;
        tree[p] = tree[L[p]] + tree[R[p]] - tree[p];
        que.push(make_pair(tree[p], p));
        L[p] = L[L[p]];
        R[L[p]] = p;
        R[p] = R[R[p]];
        L[R[p]] = p;
    }
    cout << ans << endl;
    return 0;
}