好吧，我一开始说这是个神级数据结构毒瘤题，后来改成神题了。
主要是贪心做法的巧妙转化：
首先发现选择的一对必须相邻，于是我们搞出差分。
然后考虑选取最小值时，最小值两侧的数要么同时选，要么都不选。
然后考虑把这三个数合起来变成sum[l] + sum[r] - sum[mid]
这样递归下去即可。
仔细思考，实在是巧妙至极啊！！！
关于代码实现：书上说要在堆和链表上建立映射关系，我觉得十分的毒瘤，打了135行结果五彩斑斓......
然后我决定放弃，不调了,采用神奇的：延迟删除法！就是取堆顶的时候判断。
堆优dijkstra就是这样做的。然后就A了....A了？？！！Ahhh
实在是...惨不忍睹。
我TM之前在干嘛。
#include <cstdio>
#include <queue>
typedef long long LL;
const int N = ; struct HeapNode {
LL val;
int p;
bool operator < (const HeapNode &x) const {
return val > x.val;
}
}; std::priority_queue<HeapNode> Q; struct ListNode {
LL val;
int pre, nex;
bool del;
}li[N]; int head, tail, top; void ListInit() {
head = N - ;
tail = N - ;
li[head].nex = tail;
li[tail].pre = head;
return;
} void insert(LL x) {
HeapNode hd;
hd.val = x;
hd.p = ++top;
Q.push(hd);
int r = tail;
int l = li[r].pre;
li[top].val = x;
li[l].nex = li[r].pre = top;
li[top].pre = l;
li[top].nex = r;
return;
} LL solve() {
HeapNode hd = Q.top();
Q.pop();
int pos = hd.p;
while(li[pos].del || li[pos].val != hd.val) {
hd = Q.top();
Q.pop();
pos = hd.p;
}
int l = li[pos].pre;
int r = li[pos].nex;
int l2 = li[l].pre;
int r2 = li[r].nex;
LL ans = hd.val;
if(l == head && r == tail) {
;
}
else if(l == head) {/// l pos r r2
li[pos].del = li[r].del = ;
li[l].nex = r2;
li[r2].pre = l;
}
else if(r == tail) {/// l2 l pos r
li[pos].del = li[l].del = ;
li[r].pre = l2;
li[l2].nex = r;
}
else{ /// l2 l pos r r2
li[l].del = li[r].del = ;
li[pos].val = li[l].val + li[r].val - ans;
li[l2].nex = li[r2].pre = pos;
li[pos].pre = l2;
li[pos].nex = r2;
hd.val = li[pos].val;
Q.push(hd);
}
return ans;
} int main() {
int k, n;
LL x, tx;
scanf("%d%d", &n, &k);
scanf("%lld", &tx);
for(int i = ; i <= n; i++) {
scanf("%lld", &x);
insert(x - tx);
tx = x;
}
LL ans = ;
for(int i = ; i <= k; i++) {
LL temp = solve();
//printf("%lld \n", temp);
ans += temp;
}
printf("%lld", ans);
return ;
}
AC代码
#include <cstdio>
#include <algorithm>
using std::swap;
typedef long long LL;
const int N = ; struct ListHeap {
struct HeapNode {
LL val;
int p;
bool operator < (const HeapNode &x) {
return val < x.val;
}
}h[N];
struct ListNode {
LL val;
int pre, nex, p;
}li[N];
int head, tail, top; ListHeap() {
head = N - ;
tail = N - ;
top = ;
li[head].nex = tail;
li[tail].pre = head;
}
inline void up(int x) {
int s = x >> ;
while(x != && h[x] < h[s]) {
swap(h[x], h[s]);
li[h[x].p].p = x;
li[h[s].p].p = s;
x = s;
s = x << ;
}
return;
}
inline void down(int x) {
int s = x << ;
while(s <= top) {
if(s < top && h[s | ] < h[s]) {
s = s | ;
}
if(h[s] < h[x]) {
swap(h[x], h[s]);
li[h[x].p].p = x;
li[h[s].p].p = s;
x = s;
s = x << ;
}
else break;
}
return;
}
inline void del(int x) {
swap(h[x], h[top]);
top--;
li[h[x].p].p = x;
up(x);
down(x);
return;
}
inline void insert(LL x) {
int r = tail, l = li[tail].pre;
int mid = ++top;
li[mid].pre = l;
li[mid].nex = r;
li[l].nex = li[r].pre = mid;
li[mid].val = x;
li[mid].p = top;
h[top].val = x;
h[top].p = mid;
up(top);
return;
}
inline LL solve() {
int mid = h[].p;
int l = li[mid].pre;
int r = li[mid].nex;
if(l == head && r == tail) {
return h[].val;
}
else if(l == head) {
del();
del(li[r].p);
r = li[r].nex;
li[l].nex = r;
li[r].pre = l;
return li[mid].val;
}
else if(r == tail) {
del();
del(li[l].p);
l = li[l].pre;
li[r].pre = l;
li[l].nex = r;
return li[mid].val;
}
else {
del(li[l].p);
del(li[r].p);
LL ans = li[mid].val;
li[mid].val = li[l].val + li[r].val - ans;
l = li[l].pre;
r = li[r].nex;
li[l].nex = li[r].pre = mid;
li[mid].pre = l;
li[mid].nex = r;
h[li[mid].p].val = li[mid].val;
up(li[mid].p);
down(li[mid].p);
return ans;
}
}
}LH; int main() {
int n, k;
LL x, tx;
scanf("%d%d%lld", &n, &k, &tx);
for(int i = ; i <= n; i++) {
scanf("%lld", &x);
LH.insert(x - tx);
tx = x;
}
LL ans = ;
for(int i = ; i <= k; i++) {
ans += LH.solve();
}
printf("%lld", ans);
return ;
}
剧毒万紫千红结构体