反悔贪心

基于小根堆的优先队列实现反悔贪心

基本思想：反悔贪心就是我们维护一个反悔堆，把想要反悔的放到堆中，然后不断贪心，如果发现可以反悔，那就反悔

 CF865D Buy Low Sell High

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans;
priority_queue<ll,vector<ll>,greater<ll>>q;//greater →less从大到小
int main()
{
	cin>>n;
	for(int i=0; i<n; i++)
	{
		ll p;
		cin>>p;
		if(q.size()&&q.top()<p)//q.size()==!q.empty() 当前可以卖 
		{
			ans+=p-q.top();//选择最佳的去卖 
			q.pop();
			q.push(p);//入堆 
		}
		q.push(p);//新元素加入反悔堆 
	}
	cout<<ans<<endl;
	return 0;
}

旅途的终点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,sum=0;
ll a[200010];
priority_queue<ll,vector<ll>,greater<ll>>q;
int main()
{
	cin>>n>>m>>k;
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	for(int i=0; i<n; i++)
	{
		q.push(a[i]);//执行q.pop()后开始进行互换操作
		if(q.size()>k)//开始反悔操作，对k后面用神力，k前的用耗生命值低的进行互换
		{
			sum+=q.top();//低生命值
			q.pop();
		}
		if(sum>=m)
		{
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<n<<endl;
	return 0;
}