CF2182E New Year’s Gifts

思路

题目中提到必须给 $i$ 号朋友买价值为 $y_i$ 的礼物，则这部分开销是不可避免的，直接从初始资金中减去。
此时对于朋友 $i$，他的贡献可以被形式化地表达为：

  • 消耗 $\Delta=z_i-y_i$ 的剩余金钱产生 $1$ 的贡献。
  • 消耗一个至少为 $x_i$ 美观度的礼盒产生 $1$ 的贡献。

且这两种操作不可重复计算。
我们可以贪心的将所有 $\Delta$ 按照大小排序，从小到大遍历所有礼盒，对于每个礼盒，找到它可以产生贡献的最大 $\Delta$，再使用这个礼盒，删除掉对应的 $\Delta$。
看到这里，我们需要一个可以支持插入、排序和删除的数据结构。
set 就非常合适。
但注意到这里面可能会出现相同元素，所以使用类似的 multiset。
还有一些细节，见代码中注释。

代码

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
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
	inline void read(T &x,Args&...args){
		read(x);
		read(args...);
	}
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=2e5+47,inf=1e18;
int T,n,m,k,ans;
vector<int>G[N];
multiset<int>s;
signed main(){
	read(T);
	while(T--){
		read(n,m,k);
		rep(i,1,m)G[i].clear();
		rep(i,1,m){
			int x;
			read(x);
			G[x].emplace_back(inf);
			//这里的inf只是一个标记，使礼盒作为最大值会被在所有美观度小于等于它的 Delta后面被遍历到 
		}
		rep(i,1,n){
			int x,y,z;
			read(x,y,z);
			k-=y;
			int dlt=z-y;
			G[x].emplace_back(dlt);
		}
		ans=0;
		s.clear();
		rep(i,1,m){
			sort(G[i].begin(),G[i].end());
			fep(j,0,G[i].size()){
				int x=G[i][j];
				if(x==inf){
					if(!s.empty()){
						s.erase(--s.end());
						//只删掉最后一个，而不是所有相同值 
						ans++;
					}
				}
				else{
					s.insert(x);
				}
			}
		}
		while(!s.empty()){
			int del=*s.begin();
			k-=del;
			if(k<0)break;
			s.erase(s.begin());
			ans++;
		}
		print(ans);puts("");
	}
}