【贪心+堆优化】数据备份

贪心

传送门：CodeVS1615

CTSC的题目，非常巧妙的思路（似乎贪心都是这样的）

首先在链上选取两个点一定是相邻的（废话不多解释）

那么求出所有相邻的差$len_1,len_2……len_{n-1}$

问题成功转化为在n-1个数中取出k个不相邻的使其和最小（注意取出k个，因为1个差代表了两个点/一条链）

到这似乎还比较容易想

然而，怎么求呢？

一看似乎可以Dp，然而似乎会TLE

于是经过乱（度）搞（娘）发现可以贪心

用堆来维护数列：

每次选一个最小的数，加上，然后删掉相邻的数，

重点：该数可能可以扩展为与其相邻的两个点，自己不选（不能扩展为别的，因为一旦不相邻那么不必把已选的给删去

于是把相邻的数之和减去取出的数，插回堆中，如果下次选了这个数表示**扩展**

如果取出的数处于边界那么就不用插回了，判断时标记一下就好（详见代码）

代码如下（似乎挺简短的，细节很多）：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define pr pair<int,int>
#define INF 1200000000
int n,m,ans,len[100030],last[100030],next[100030],a[100030];
priority_queue < pr, vector<pr>, greater<pr> >h;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	for (int i=2;i<=n;i++){
		len[i]=a[i]-a[i-1];
		h.push(make_pair(len[i],i));
		next[i]=i+1;
		last[i]=i-1;
	}
	last[2]=next[n]=0;//mark,len[] start at 2 but not 1
	
	while (m--){
		while (h.top().first!=len[h.top().second]) h.pop();
		
		int u=h.top().second; h.pop();
		int l=last[u],r=next[u];
		ans+=len[u];
		
		next[last[u]=last[l]]=u;
		last[next[u]=next[r]]=u;
		len[u]=(l&&r)?(len[l]+len[r]-len[u]):INF;
		//if l==0 || r==0 len[u]=INF
		//判断边界
		len[l]=len[r]=INF;
		
		h.push(make_pair(len[u],u));
	}
	
	printf("%d\n",ans);
	
	return 0;
}