原题:P1484 种树

测评链接:R168538881 记录详情

描述:

1A1T8W,已过样例

思路:

贪心，链表存点，用大根堆维护，每次种下一颗树之后，就将俩边反悔的价值加入堆中，并把链表合起来维护，用$vis[i]$维护$pos[i]$的懒惰标记，防止重复种树。

代码:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int n,k,ans;
struct node{
	int id;
	int pre,nxt;
	int val;
	bool operator < (const node &rhs)const{
		return val == rhs.val?id < rhs.id :val < rhs.val;
	}
	bool operator > (const node &rhs)const{
		return val == rhs.val?id > rhs.id :val > rhs.val;
	}
}pos[300005]; 
priority_queue<node> q;
bool visd[300005];

void mid_merge(node m1,node &m2,node m3,node &pr,node &nt)
{
	m2.val = m1.val + m3.val - m2.val;
	m2.pre = pr.id;
	m2.nxt = nt.id;
	pr.nxt = m2.id;
	nt.pre = m2.id;
} 

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i = 1;i <= n;i++)
	{
		cin>>pos[i].val;
		pos[i].pre = i - 1;
		pos[i].nxt = i + 1;
		pos[i].id = i;
		q.push(pos[i]);
	}
	while(k--)
	{
		node cnt = q.top();
		q.pop();
		while(visd[cnt.id]) cnt = q.top(),q.pop();
		if(cnt.val < 0) break;
		ans += cnt.val;
		mid_merge(pos[cnt.pre],pos[cnt.id],pos[cnt.pre],pos[pos[cnt.pre].pre],pos[pos[cnt.nxt].nxt]);
		visd[pos[cnt.pre].id] = visd[pos[cnt.nxt].id] = true;
	}
	cout<<ans;
} 

跪谢大佬调程序