题解 P1792 【[国家集训队]种树】
Kuriyama_Mirai
·
·
题解
其实这道题就是一道可反悔的贪心+大根堆+双向链表。
堆（大根堆）
大根堆的定义就是一棵完全二叉树，但是它满足一个重要的性质：一个节点的权值一定比它所有子节点要大。
小根堆就是比子节点要小。
维护就很容易了，见代码（当然你也可以用priority_queue，用法自行度娘）
双向链表
双向链表的定义就是对于每一个节点，都存储它的左边的节点的地址和右边节点的地址。比如下面就是一个以int为节点的结构体：
struct node {
int val;
node* left, right;
}
这里用的是%你模拟链表：
int val[Max_N], left[Max_N], right[Max_N];
其实都差不多，但是left[i]不再存储i的val[i]的左节点的地址，而存的是下标。
可反悔的贪心
如果我们用正常的贪心去做，一定会\color{red}\mathcal{WA}。
（比如 19 20 19 1）这个点
但是如果你用了这种方法来取的话，就能\color{green}\mathcal{AC}：
对于每一个节点，如果这个节点要种树，就让这个树的权值进行如下操作：
这样子，只要你接下来想取这个点的两边（而不是取这个点）的话，就可以在``total``的值上从$val[i]$变为$val[l[i]]+val[r[i]]$。
## 接下来是代码：
```cpp
#include <cstdio>
using namespace std;
#define size() (now - 1)
#define empty() (now == 0)
#define top() (heap[1])
#define INF 0x3f3f3f3f
#define max_n 200001
struct pii {
int v, i;
};
bool operator < (const pii& , const pii&);
bool operator > (const pii& , const pii&);
void swap(pii &, pii &);
void push(const pii&);
void pop();
pii _pair(const int& ,const int&);
pii heap[200001];
int num[max_n], L[max_n], R[max_n];
int now = 1;
bool go[max_n];
int main() {
int n, m, total = 0;
pii x;
scanf("%d%d", &n, &m);
if ((m << 1) > n) { // 根本种不下
printf("Error!");
return 0;
}
for (int i = 1; i <= n; i ++) { // 定义一个链表
scanf("%d", &num[i]);
L[i] = i - 1;
R[i] = i + 1;
push(_pair(num[i], i));
}
L[1] = n;
R[n] = 1;
for (int i = 0; i < m; i ++) {
while (not empty() and go[top().i]) // 先把所有已经种树的点给pop掉
pop();
x = top();
pop();
total += x.v;
num[x.i] = x.v = num[L[x.i]] + num[R[x.i]] - x.v; // 合并节点
go[L[x.i]] = go[R[x.i]] = true; // 删除节点
L[x.i] = L[L[x.i]];
R[x.i] = R[R[x.i]];
L[R[x.i]] = R[L[x.i]] = x.i;
push(x);
}
printf("%d", total);
return 0;
}
void pop() {
heap[1] = heap[--now];
heap[now + 1].v = -INF;
int k = 1, i;
while ((k << 1) <= now) {
i = k << 1;
if (heap[i] < heap[i + 1])
i ++;
if (heap[k] < heap[i])
swap(heap[k], heap[i]);
else
break;
k = i;
}
}
bool operator < (const pii &x, const pii &y) {
return x.v < y.v;
}
bool operator > (const pii &x, const pii &y) {
return x.v > y.v;
}
void swap(pii &x, pii &y) {
pii z;
z = x;
x = y;
y = z;
}
void push(const pii &in) {
heap[now ++] = in;
int k = now - 1;
while (k xor 1 and heap[k] > heap[k >> 1]) {
swap(heap[k], heap[k >> 1]);
k >>= 1;
}
}
pii _pair(const int &v ,const int &i) {
pii x;
x.v = v;
x.i = i;
return x;
}
```