P 3045[USACO 12 FEB]牛券Cow Coupons欲張り+優先行列

タイトルリンク
貪欲な考え:
0.欲張り撤回
1.まず、すべての乳牛がクーポンを使用している場合、割引価格が最も少ない前のK個の乳牛は必ず最終的な答えに含まれます.そうでなければ、K+1~N区間の乳牛にクーポンが使われていることを意味しますが、前のK個の乳牛のうちの1個は選ばず、明らかにお得ではなく、状況が最適ではありません.
2.並べ替えられた前K個の乳牛に対して全てクーポンを使用することを考慮し、小さいものから大きいものまで保存(P[i]-C[i])するスタックメンテナンスを再構築し、[K+1,N]個の乳牛を選択する場合、スタックトップを比較する
同時に[k+1,n]要素を元の価格でソートします.

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 50001;
const int INF = 0X3F3F3F3F;

#define lint long long


lint N,K,M;

struct _Cow
{
	int Price;
	int AfterPrice;
}Cow[MAXN];

priority_queue,greater > Queue1;

lint ans = 0;

bool cmp1(_Cow a,_Cow b)
{
	return a.AfterPrice < b.AfterPrice;
}

bool cmp2(_Cow a,_Cow b)
{
	return a.Price < b.Price;
}

void Solve(void)
{
	sort(Cow+1,Cow+1+N,cmp1);
	
	lint Sum = 0;
	for(int i = 1;i <= K;i++)
	{
		Sum += Cow[i].AfterPrice;
		if(Sum > M)
		{
			ans = i-1;
			return;
		}
		if(i == N)
		{
			ans = N;
			return;
		}
		Queue1.push(Cow[i].Price-Cow[i].AfterPrice);
	}
	
	sort(Cow+1+K,Cow+1+N,cmp2);
	ans = K;
	for(int i = K+1;i <= N;i++)
	{
		lint MinOff = Queue1.top();
		
		if(MinOff < Cow[i].Price-Cow[i].AfterPrice && !Queue1.empty())    //          
		{
			Sum += MinOff;
			Sum += Cow[i].AfterPrice;
			Queue1.pop();
			Queue1.push(Cow[i].Price-Cow[i].AfterPrice);
		}
		else
		{
			Sum += Cow[i].Price;
		}
		if(Sum > M)
		{
			return;
		}
		ans++;
	}
	return;
};

int main(void)
{
	cin >> N >> K >> M;
	for(int i = 1;i <= N;i++)
	{
		cin >> Cow[i].Price >> Cow[i].AfterPrice;
	}
	
	Solve();
	cout << ans << endl;
	
	return 0;
}