【优先队列】洛谷 P3045 Cow Coupons G
2021-03-14 00:41:00 # ACM

题链

贪心把使用优惠劵后价格前$K$个一一压入队列（以队列 $QQ$ 表示）直到钱不够（可以证明前$K$个是一定要买的，因为最赚），其他未被压入队列的价格压入队列 $Q$

例如价格前$K$个中某个产品以原价购买$+$后$K$个某个产品以优惠价购买也是可行的情况

1
2
3
2 1 5
2 1
1000 3

则 $QQ$队列中以原价和优惠价的差值从小到大排序，$Q$ 队列中以优惠价从小到大排序，判断 $Q$队列中能否加入到 $QQ$队列；

$Q$队列中是优惠价从小到大，若优惠价相同，则以原价从大到小排，因为这样最优且最赚；

若遍历 $Q$队列的时候，钱已经不够了（意味着优惠卷的使用已经到极限了），则需要再定义一个 $QQQ$队列存放未被买过的产品且以 原价 从小到大排序，用原价尝试剩余产品；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 500009
#define INF 1e18
#define mod 998244353
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define eps 1e-9

LL n,m,k;
struct node{
	LL a,b,pos; // 优惠价,原价 
}p[MS];
LL v[MS];

struct nod{
	LL a,b,pos;
};

bool cmp(node x,node y){
	return x.b < y.b;
}

bool operator < (node x,node y){
	if(x.b == y.b) return x.a < y.a;
	return x.b > y.b;
}

bool operator < (nod x,nod y){
	return x.a - x.b > y.a - y.b;
}

priority_queue<node > Q;
priority_queue<nod > QQ;
priority_queue<LL,vector<LL>,greater<LL> > QQQ;

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		LL t1,t2;
		cin >> t1 >> t2;
		p[i] = {t1,t2,i};
	}
	sort(p+1,p+n+1,cmp);
	/*cout << " ----------------- " << endl;
	for(int i=1;i<=n;i++){
		cout << p[i].a << " " << p[i].b << " " << p[i].pos << endl;
	}
	cout << " ------------------ " << endl;*/
	LL ans = 0;
	for(int i=1;i<=m && k-p[i].b>=0;i++){
		QQ.push({p[i].a,p[i].b,p[i].pos});
		k -= p[i].b;
		v[p[i].pos] = 1;
		ans++;
	}
	for(int i=1;i<=n;i++){
		if(!v[p[i].pos]){
			Q.push(p[i]);
		}
	}
	while(!Q.empty() && !QQ.empty()){
		nod e1 = QQ.top();
		node e2 = Q.top();
		if(k-(e1.a-e1.b)-e2.b < 0) break;
		k = k-(e1.a-e1.b)-e2.b;
		ans++;
		QQ.pop();
		QQ.push({e2.a,e2.b,e2.pos});
		v[e2.pos] = 1; 
		Q.pop();
	}
	for(int i=1;i<=n;i++){
		if(!v[p[i].pos]){
			QQQ.push(p[i].a);
		}
	}
	while(!QQQ.empty()){
		LL e = QQQ.top();
		if(k - e < 0) break;
		k -= e;
		ans++;
		QQQ.pop();
	}
	cout << ans << endl;
	
	return 0;
}
Prev
2021-03-14 00:41:00 # ACM
Next