BZOJ1150 - [APIO2007][CTSC2007]数据备份Backup

2017/01/02

一道看起来是 DP 的贪心。

题目描述

你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。然而数据备份的工作是枯燥乏味的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣。已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而,网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆,这意味着你仅能为 K 对办公楼(或总计2K个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说,这 2K 个办公楼一定是相异的)。此外,电信公司需按网络电缆的长度(公里数)收费。因而,你需要选择这 K 对办公楼使得电缆的总长度尽可能短。换句话说,你需要选择这 K 对办公楼,使得每一对办公楼之间的距离之和(总距离)尽可能小。下面给出一个示例,假定你有 5 个客户,其办公楼都在一条街上,如下图所示。这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。 上例中最好的配对方案是将第 1 个和第 2 个办公楼相连,第 3 个和第 4 个办公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km-1km=2km ,第 2 条电缆的长度是 6km-4km=2km。这种配对方案需要总长 4km 的网络电缆,满足距离之和最小的要求。

解题思路

因为电缆只可能在相邻的大楼之间连接,所以说先对位置做一下差分得到各个距离段的长度。然后问题转化为在 N-1 个数中取 K 个互不相邻的数,使他们的和最小。

那么可以把所有的分段按长度扔到优先队列里: 1. 取出当前队列中最小的元素 x 2. ans += x 3. 删除 x, x左侧的元素l , x右侧的元素r 4. 插入 l+r-x

如果取当前这一段x不如取左右两段好的话,在之后贪心的过程中就会取到 l+r-x, 更新答案的时候会把原来的恰好抵消掉。

代码

堆的点删值得学习一下。

 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
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int SIZ = 2E6;
const int _oo = 0x3f3f3f3f;
int N, K, y, len[SIZ], pre[SIZ], nxt[SIZ], ans;
priority_queue<PII, vector<PII>, greater<PII> > Q;

int main() {
    scanf("%d %d", &N, &K);

    int x;
    for(int i=1;i<=N;i++) {
        scanf("%d", &x);
        len[i] = x - y, y = x;
        if(i != 1) Q.push(make_pair(len[i], i));
        pre[i] = i-1; nxt[i] = i+1;
    }
    
    pre[2] = 0; nxt[N] = 0;

    while(K--) {
        while(Q.top().first != len[Q.top().second]) Q.pop();
        int u = Q.top().second, l = pre[u], r = nxt[u]; Q.pop();
        ans += len[u];
        len[u] = l && r ? len[l] + len[r] - len[u] : _oo;
        pre[nxt[u] = nxt[r]] = u;
        nxt[pre[u] = pre[l]] = u;
        len[l] = len[r] = _oo;
        Q.push(make_pair(len[u], u));
    }

    printf("%d\n", ans);
}