博客

数据备份BZOJ1150

思路

题干在这：

BZOJ1150


我们注意到选取的一定是相邻的边，那我们先求出两两之间相隔的距离d[i]。可知如果我们选了d[i]，那么我们就不能选d[i-1]和d[i+1]。我们每次找到一个最小的值d[i]，并把d[i]，d[i-1]和d[i+1]删去；我们又要保留选d[i-1]和d[i+1]的可能性，所以再在原位插进去值为d[i-1]+d[i+1]-d[i]的点。

我们用一个优先队列得到最小值，并用np和pp记录某个点下一个点和上一个点的位置，并且每次操作实时更新。

注意边界条件，如果选了边上的点，则该点边上的点一定不会被选，所以直接删去这两个点就好。

为了防止复杂的讨论，在两端插入值为inf的点，这两个点显然不会被选，简化了操作

ac代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define N 100010
#define inf 0x3f3f3f3f
using namespace std;
int locate[N] = { 0 };
struct point {
	int val;
	int self;
	friend bool operator<(const point& a, const point& b) {
		return a.val > b.val;
	}
}distant[N];
int mark[N];
int np[N], pp[N];
priority_queue<point> solve;
int main() {
	int n, k;
	long long sum = 0;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> locate[i];
	distant[0].val = inf;
	distant[n].val = inf;
	solve.push(distant[0]);
	solve.push(distant[n]);
	for (int i = 1; i < n; i++) {
		distant[i].val = locate[i + 1] - locate[i];
		np[i] = i + 1;
		distant[i].self = i;
		pp[i] = i - 1;
		solve.push(distant[i]);
	}
	while (1) {
		while (solve.size()&&mark[solve.top().self])
			solve.pop();
		if (k == 0 || solve.size() == 0) {
			cout << sum;
			return 0;
		}
		point mid = solve.top();
		solve.pop();
		sum += mid.val;
		if (np[mid.self] == n) {
			np[pp[pp[mid.self]]] = n;
			mark[pp[mid.self]] = 1;
		}
		else if (pp[mid.self] == 0) {
			pp[np[np[mid.self]]] = 0;
			mark[np[mid.self]] = 1;
		}
		else {
			mark[np[mid.self]] = 1;
			mark[pp[mid.self]] = 1;
			point insert;
			insert.val = distant[np[mid.self]].val + distant[pp[mid.self]].val - mid.val;
			insert.self = mid.self;
			distant[insert.self].val = insert.val;
			np[mid.self] = np[np[mid.self]];
			pp[np[mid.self]] = mid.self;
			pp[mid.self] = pp[pp[mid.self]];
			np[pp[mid.self]] = mid.self;
			solve.push(insert);
		}
		k--;
	}
}