【洛谷】【堆+贪心】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);

 }

巴特西

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

最新文章

热门文章