LuoguP3045牛券Cow Coupons

LuoguP3045 [USACO12FEB]牛券Cow Coupons

果然我贪心能力还是太差了

ZR讲过的原题我回来对做法没有一丁点印象

有时候有这样一种题目

每个数有两种不同的价值

你可以选择价值低的,也可能花费一些神秘能力去获得价值高的

这时候我们直接贪心就可能会出现这种情况

当前最后解不是全局最优解

一般这种时候有两节决策,

要么DP

要么尝试进行可反悔的贪心

我们先按照所有牛的优惠后的价格排序,开一个小根堆

将前\(k\)个用优惠劵去买,很明显这可能是错误的

我们就将优惠券买的每一头牛的\(p - c\)丢到堆中,

对于一头使用了优惠券的牛\(i\)和未使用优惠券的牛\(j\)

如果有

\[c_i+p_j > c_j+p_i
\]

那么说明把优惠券用到\(j\)上更优

那么我们就把后\(n - k\)头牛按照\(p\)排序

每次看一看反悔是否更优就好了

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<LL,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 1e5 + 3;

priority_queue <pii,vector<pii>,greater<pii> > q;

LL n,m,k;int ans;

struct node{

	LL p;

	LL c;

}a[N];

bool book[N];

LL sum,tot;

inline bool cmp(node x,node y){

	return x.c < y.c;

}

inline bool cmpp(node x,node y){

	return x.p < y.p;

}

inline LL read(){

	LL v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

int main(){

	n = read(),k = read(),m = read();

	for(int i = 1;i <= n;++i) a[i].p = read(),a[i].c = read();

	sort(a + 1,a + n + 1,cmp);

	LL sum = 0;

	for(int i = 1;i <= k;++i){

		sum += a[i].c;

		if(sum > m){

			printf("%d\n",i - 1);

			return 0;

		}

		q.push(mk(a[i].p - a[i].c,i));

	}

	ans = k;

	sort(a + k + 1,a + n + 1,cmpp);

	for(int i = k + 1;i <= n;++i){

		pii x = q.top();

		if(a[x.se].c + a[i].p > a[x.se].p + a[i].c){

			ans++;

			sum = sum - a[x.se].c;

			sum = sum + a[i].c + a[x.se].p;

			q.pop();

			q.push(mk(a[i].p - a[i].c,i));

		}

		else{

			ans++;

			sum += a[i].p;

		}

		if(sum > m) {printf("%d\n",ans - 1);return 0;}

	}

	printf("%lld\n",n);

	return 0;

}