BZOJ1150: [CTSC2007]数据备份Backup

1150: [CTSC2007]数据备份Backup

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2357 Solved: 957
[Submit][Status][Discuss]

Description

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

　　上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km-1km=2km ，第 2 条电缆的长度是 6km-4km=2km。这种配对方案需要总长 4km 的网络电缆，满足距离之和最小的要求。

Input

　　输入的第一行包含整数n和k，其中n（2 ≤ n ≤100 000）表示办公楼的数目，k（1≤ k≤ n/2）表示可利用的网络电缆的数目。接下来的n行每行仅包含一个整数（0≤ s ≤1000 000 000）, 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

Output

　　输出应由一个正整数组成，给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。

Sample Input

5 2
1
3
4
6
12

Sample Output

HINT

Source

【题解】

可以证明一定要选相邻的对。

先把原数组差分，问题转化成在差分数组中选择k个数，这k个数互不相邻且和最小

对于差分数组中最小的，要么选这个最小的，要么选他两边的数且两个都要选

选了最小的，导致相邻两个不能选，而再选两个可能不如相邻两个更优

相邻两个不能只选一个，如果只选一个，倒不如选这个最小的

有没有可能三个都不选呢？肯定是不可能的。如果都不选，那么答案里的一个数换成最小的，仍然更优

有了这个结论，就可以用堆贪心

优先选最小的num[i]，然后加入反悔机制，不选最小的，选他相邻的,

把num[i -> pre] + num[i -> nxt] - num[i]换到num[i]的地方，并压入堆

用双向链表维护

可以证明每次从堆里选一个，就一定使选的个数+1

怎么证明结论是最优的呢？

原题是n个数选k个

每次选一个数，变成n - 3个数选k - 1个（边界虚一个点，正无穷大，因为边界点没法选周围两个点）

把n-2个数看做地位平等的n-2个数，即使他是合起来的，其实也一个样

然后有结论，要么选这个最小的，要么选他两边的数且两个都要选，上面证明过

于是选最小的就可以了

不太严谨

 1 /**************************************************************
 2     Problem: 1150
 3     User: 33511595
 4     Language: C++
 5     Result: Accepted
 6     Time:672 ms
 7     Memory:95816 kb
 8 ****************************************************************/
 9  
10 #include <iostream>
11 #include <cstdio>
12 #include <cstring>
13 #include <cstdlib>
14 #include <queue>
15 #include <vector>
16  
17 inline void read(int &x)
18 {
19     char ch = getchar(), c = ch;x = 0;
20     while(ch < '0' || ch > '9')c = ch, ch = getchar();
21     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
22     if(c == '-')x = -x;
23 }
24  
25 const int INF = 0x3f3f3f3f;
26 const int MAXN = 1000000 + 10;
27 const int MAXM = 1000000 + 10;
28  
29 int n,m,cnt,b[MAXN << 2],ans,num,tmp;
30  
31 struct Node
32 {
33     int pre,nxt,value,num,cnt;
34     Node(int _pre, int _nxt, int _value, int _num, int _cnt){pre = _pre, nxt = _nxt, value = _value, num = _num;cnt = _cnt;}
35     Node(){}
36 }node[MAXN << 2];
37  
38 struct cmp
39 {
40     bool operator()(int a, int b)
41     {
42         return node[a].value > node[b].value;
43     }
44 };
45  
46 std::priority_queue<int, std::vector<int>, cmp> q;
47  
48 int main()
49 {
50     read(n), read(m);
51     read(tmp);
52     for(register int i = 2;i <= n;++ i) 
53     {
54         read(num);
55         ++ cnt;
56         node[cnt] = Node(cnt - 1,cnt + 1,num - tmp,1,cnt);
57         tmp = num;
58         q.push(cnt);
59     }
60     node[0] = Node(0,1,INF,0,0);++cnt;
61     node[cnt] = Node(cnt - 1,0,INF,0,cnt);
62     register int tmp,pre,nxt;
63     int now = 0;
64     while(q.size() && now < m)
65     {
66         tmp = q.top(), q.pop();
67         pre = node[tmp].pre, nxt = node[tmp].nxt;
68         if(b[node[tmp].cnt])continue;
69         if(now + node[tmp].num > m)continue;
70         b[node[tmp].cnt] = b[node[pre].cnt] = b[node[nxt].cnt] = 1; 
71         ans += node[tmp].value;
72         now += node[tmp].num;
73         ++cnt;
74         node[node[pre].pre].nxt = cnt;
75         node[node[nxt].nxt].pre = cnt;
76         node[cnt] = Node(node[pre].pre, node[nxt].nxt, node[pre].value + node[nxt].value - node[tmp].value, node[pre].num + node[nxt].num - node[tmp].num, cnt);
77         q.push(cnt);
78     }
79     printf("%d", ans);
80     return 0;
81 }

BZOJ1150

秒客网