题目大意
在一个线段上,顺序给出 n 个点到线段一端的距离。要求用 k 条边连接一共 2k 个不同的点,边权即为距离。求最小边权和。
2⩽n⩽100,000,1⩽k⩽2n
题目链接
【APIO/CTSC 2007】数据备份 - Luogu 3620
题解
优先队列 + 双向链表 + 乱搞(说「乱搞」是因为确实没有什么可说成是算法的东西。。。不过,那个时候,优先队列的实现没记错应该是手写的,也就是说,这道题本应该是像 Splay 题之类的差不多的数据结构题。。。应该。。。)
首先,显然答案中连接的边不会交叉,所以原题可描述为:给定长为 n−1 的正整数数列,不连续地选出 k 个数的最小值。
把数列建成双向链表,两头是空指针,同时把所有节点放入优先队列/小根队。
每次取出一个节点,删除它以及前后两个节点(实际给节点打标记,取出来后发现被删除了就继续循环),并在原来的位置上插入一个权值为 prev.key+next.key−key 、代表个数为 prev.cnt+next.cnt−cnt 的节点,当选到时,表示「反悔」选择当前节点并改选两侧节点。一直循环下去,每次减去选出节点的代表个数,直至 k 个数被取完。
代码
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include <cstdio> #include <climits> #include <queue> #include <algorithm> const int MAXN = 100005; struct Node { long long key; int cnt; bool del; Node *prev, *next; Node() {} Node(long long key, int cnt, Node *prev, Node *next) : key(key), cnt(cnt), prev(prev), next(next), del(false) {} long long getCombineKey() { long long res = -key; if (prev) res += prev->key; else res += INT_MAX; if (next) res += next->key; else res += INT_MAX; return res; } long long getCombineCnt() { long long res = -cnt; if (prev) res += prev->cnt; else res += INT_MAX; if (next) res += next->cnt; else res += INT_MAX; return res; } } d[MAXN]; struct cmp { bool operator()(Node *a, Node *b) { return a->key > b->key; } }; int main() { int n, k; scanf("%d %d", &n, &k); std::priority_queue<Node *, std::vector<Node *>, cmp> q; for (int i = 0, last, curr; i < n; i++, last = curr) { scanf("%d", &curr); if (!i) continue; d[i] = Node(curr - last, 1, i != 1 ? &d[i - 1] : NULL, i != n - 1 ? &d[i + 1] : NULL); q.push(&d[i]); } long long ans = 0; while (k > 0) { Node *u = q.top(); q.pop(); if (u->del) continue; u->del = true; if (u->prev) u->prev->del = true; if (u->next) u->next->del = true; ans += u->key; k -= u->cnt; u = new Node(u->getCombineKey(), u->getCombineCnt(), u->prev ? u->prev->prev : NULL, u->next ? u->next->next : NULL); if (u->prev) u->prev->next = u; if (u->next) u->next->prev = u; q.push(u); } printf("%lld\n", ans); return 0; }
|