[数据结构与算法]工作安排（反悔贪心板子题）

工作安排 - 题目 - Daimayuan Online Judge

分析：

• 贪心，将set当链表用

  从后往前考虑（这样先入队的就一直能到最后），碰到更小的时刻，就将之前入队的 能出的全出

#include <bits/stdc++.h>
#define int long long 
#define Pa pair<int,int> 
using namespace std;

const int N=1e5+5;
struct node 
{
	int d,p;
	bool operator < (node b) const { return d<b.d || d==b.d && p<b.p; }
}a[N];
set <int> st;
void solve()
{
    int n;
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld%lld",&a[i].d,&a[i].p);
		st.insert(a[i].d);
	}
	sort(a+1,a+1+n);
	auto it=prev(st.end());
	int l,r=*it;
	if(it==st.begin()) l=0;
	else it=prev(it), l=*it;
	int ans=0;
	priority_queue <int,vector<int>,less<int> > q;
	for(int i=n;i>=0;i--)
	{
		if(a[i].d==l) 
		{
			while(r>l && !q.empty()) 
			{
				r--;
				ans+=q.top(); q.pop();
			}
			if(it!=st.begin()) it=prev(it), r=l, l=*it;
			else l=0;
		}
		q.push(a[i].p); 
	}
	cout<<ans<<"\n";
}
signed main()
{
    int T=1;
    //cin>>T;
    while(T--) solve();
}

solution 2:

• 贪心+考虑容斥（反悔贪心板子题，我是zz）

  考虑何时才要出队

#include <bits/stdc++.h>
#define int long long 
#define Pa pair<int,int> 
using namespace std;

const int N=1e5+5;
struct node 
{
	int d,p;
	bool operator < (node b) const { return d<b.d || d==b.d && p<b.p; }
}a[N];
void solve()
{
    int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld%lld",&a[i].d,&a[i].p);
		ans+=a[i].p;
	}
	sort(a+1,a+1+n);
	int cnt=0;
	priority_queue <int,vector<int>,greater<int> > q;
	for(int i=1;i<=n;i++)
	{
		q.push(a[i].p);
		cnt++;
		if(cnt>a[i].d) 
		{
            // cnt 大于当前的时刻，说明不足以完成（包括）当前的时刻之前的所有工作，要剔除最小的
			ans-=q.top(); q.pop();
			cnt--;
		}
	}
	cout<<ans<<"\n";
}
signed main()
{
    int T=1;
    //cin>>T;
    while(T--) solve();
}