【洛谷】【堆+贪心】P1484 种树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题目描述：】

cyrcyr今天在种树，他在一条直线上挖了n个坑。这n个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够，他至多会种k棵树。假设cyrcyr有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。

【输入格式：】

第一行，两个正整数n,k。

第二行，n个正整数，第i个数表示在直线上从左往右数第i个坑种树的获利。

【输出格式：】

输出1个数，表示cyrcyr种树的最大获利。

输入样例#： - -
输出样例#：

输入输出样例

【算法分析：】

这时一道贪心的题目：

对于一个树坑i，有两种状态：种树或者不种树

当选择树坑i种树时，获利为a[i]

而也可以选择在(i - 1)和(i + 1)两个位置种树，所以将a[i]更新成a[i - 1] + a[i + 1] - a[i]

利用大根堆每次寻找最大值，并将更改后的值再次push进堆里

如果选择i后又选择了(i - 1)和(i + 1)，更新时 - a[i]的操作就显得不可或缺了= =

利用堆优化后的算法复杂度为O(k log₂ n)

【代码：】

//种树
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector> #define pii pair<int, int>
#define mkp make_pair
#define fi first
#define se second
using namespace std; const int MAXN = + ; priority_queue<pii> q; int n, k;
int a[MAXN], l[MAXN], r[MAXN];
bool tree[MAXN];
long long ans; int main() {
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
q.push(mkp(a[i], i));
l[i] = i - , r[i] = i + ;
}
r[] = , l[n + ] = n;
while(k--) {
while(tree[q.top().se]) q.pop();
pii tmp = q.top();
q.pop();
if(tmp.fi <= ) break;
ans += tmp.fi;
int pos = tmp.se;
a[pos] = a[l[pos]] + a[r[pos]] - a[pos];
tmp.fi = a[pos];
tree[l[pos]] = tree[r[pos]] = ;
l[pos] = l[l[pos]], r[l[pos]] = pos;
r[pos] = r[r[pos]], l[r[pos]] = pos;
q.push(tmp);
}
printf("%lld\n", ans);
}