题解 P6538 [COCI2013-2014#1] LOPOV

cjh20090318 · 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)。

谢谢大家 ！