1 条题解
-
1
大家好,我是 CQ-C2024 蒟蒻 CJH。
洛谷博客。
题意
题目描述很清楚了不说。标签:排序,贪心。
分析
此题要让价值最大化,就要在每一个袋子的容量内选取最大价值的物品,这个可以使用手写大根堆或是使用
STL priority_queue
,具体使用方法请自行 BDFS。注意事项
- 容量为 的袋子中有可能会没有符合条件的物品,所以在取出堆顶前要判断堆中是否为空,
就因为这个不起眼的判断我失去了一大半的分数。 - 根据数据范围 ,,答案需要用
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; }
时间复杂度 。
谢谢大家 !
- 容量为 的袋子中有可能会没有符合条件的物品,所以在取出堆顶前要判断堆中是否为空,
- 1
信息
- ID
- 5443
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- 4
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者