自动搬运

查看原文

来自洛谷，原作者为

	cjh20090318 求知若饥，虚心若愚。即使我无法如你一般成为照亮云端的雷霆，但也可以做黑夜里的一缕烛火。

搬运于2025-08-24 22:21:43，当前版本为作者最后更新于2022-10-21 22:36:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家好，我是 CQ-C2024 蒟蒻 CJH。

题意

题目描述很清楚了不说。

标签：排序，贪心。

分析

此题要让价值最大化，就要在每一个袋子的容量内选取最大价值的物品，这个可以使用手写大根堆或是使用 STL priority_queue，具体使用方法请自行 BDFS。

注意事项

• 容量为 $C_i$ 的袋子中有可能会没有符合条件的物品，所以在取出堆顶前要判断堆中是否为空，就因为这个不起眼的判断我失去了一大半的分数。

• 根据数据范围 $1 \le N,K \le 3 \times 10^5$，$1 \le C_i \le 10^8$，答案需要用 long long 存储，不开 long long 见祖宗。

代码

//the code is from chenjh
#include<cstdio>
#include<algorithm>
#include<queue>
#define MAXN 300003
using namespace std;
int n,k;
//int m[MAXN],v[MAXN];
struct BREAD{//每一个物体的重量和价值。
	int m,v;
}a[MAXN];
bool cmp(BREAD x,BREAD y){return x.m<y.m||(x.m==y.m&&x.v<y.v);}//每个物体按重量从小到大排序。
priority_queue<int> Q;//大根堆，存储物体的价值。
int c[MAXN];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].m,&a[i].v);
	for(int i=1;i<=k;i++) scanf("%d",&c[i]);
	sort(c+1,c+k+1);//将袋子按容量从小到大排序。
	sort(a+1,a+n+1,cmp);//见排序函数。
	long long ans=0;int j=1;
	for(int i=1;i<=k;i++){//从 1~k 进行枚举。
		for(;j<=n && a[j].m<=c[i];j++) Q.push(a[j].v);//将符合要求的物品的价值放入堆中。
		if(!Q.empty())ans+=Q.top(),Q.pop();//只有在堆不为空时才能取出堆顶（最大价值）！
	}
	printf("%lld\n",ans);
	return 0;
}

时间复杂度 $O(n \log n)$。

谢谢大家 ！