problem
- 在一条直线上有n个坑,要种k棵树。
- 不能在相邻两个坑种树。
- 已知在每个坑种树会有一个获利,求最大获利。
- n<=5e5,k<=n/2
solution
- 考虑限制条件:对于每个位置id,我们都可以选择ans = max(v[id], v[ l[ id ] ]+v[ r[ id ]])
- 贪心:首先将全部的坑丢入大根堆中,然后从枚举1到k,每次取出获利最大的坑种树。最多种满k个坑(可以中不满,为负的话去种它就没有意义)
- 限制:对于限制条件,我们采用缩点(对于每个点,不管选择了v[id]还是v[l[id]]+v[r[id]], 这三个位置肯定都不能用了,且选择v[l[id]]+v[r[id]]时他们左右的两个坑也没用了。于是我们新建一个点num代替这三个点,把l[l[id]],r[r[id]]连到num,再维护其左右端点值。) + 后悔(我们在堆中维护v[l[id]]+v[r[id]]-v[id],那么如果下次取出来一个正数,相当于没选之前选的v[id]而选择了新的v[l[id]]+v[r[id]]。同时相当于选择了缩点后的新节点,反之则没有[此时堆中节点值为为负数所以才不会选中,相当于新节点没选,也不需要更新左右节点值]。将新节点与左右两个坑中的节点比较作差丢入堆中。)
codes
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 5e5+10;
struct node{
int id, val;
node(int id, int val):id(id),val(val){}
bool operator < (const node & b)const{return val<b.val;}
};
priority_queue<node>q;
int l[maxn], r[maxn], data[maxn], ok[maxn];
int main(){
int n,k; cin>>n>>k;
for(int i = 1; i <= n; i++){
cin>>data[i]; q.push(node(i,data[i]));
l[i] = i-1, r[i] = i+1;
}
r[0] = 1, l[n+1] = n;
long long ans = 0;
for(int i = 1; i <= k; i++){
while(ok[q.top().id])q.pop();
node t = q.top(); q.pop();
if(t.val < 0)break;
ans += t.val;
int x = t.id;
data[t.id] = data[l[t.id]]+data[r[t.id]]-data[t.id];
ok[l[t.id]] = 1; ok[r[t.id]] = 1;
l[t.id] = l[l[t.id]]; r[l[t.id]] = t.id;
r[t.id] = r[r[t.id]]; l[r[t.id]] = t.id;
q.push(node(x,data[t.id]));
}
cout<<ans<<'
';
return 0;
}