题解 P6538 【[COCI2013-2014#1] LOPOV】

⚡小林子⚡ · 2020-07-19 12:14:49 · 题解

题目传送门

这题我刚看到的时候：

~~袋子，物品，这是背包啊！~~

把题读完才发现，这题是一道裸的贪心。

为什么是贪心：~~你没有发现这题跟纪念品分组挺像的吗~~

形容不好，大概就是一种直觉告诉我不是 DP，然后这题就是贪心了。

然后就可以想想怎么贪心了。

首先排序肯定是必不可少的，把物品按照重量从小到大排，把袋子按容量从小到大排。
然后 for 循环枚举每个袋子，在能装的物品里选价值最大的即可。

时间复杂度：枚举袋子 \Theta(K)，枚举物品 \Theta(N)，总复杂度 \Theta(NK)，

看一眼数据范围：

1\le N,K\le 3\times 10^5

除非您会使用指令集，否则肯定会炸。

~~Let's think about other ways.~~

枚举袋子肯定是少不掉的，我们试着在枚举物品上面做优化。

这里有一种思路：用优先队列按价值从大到小维护当前体积不大于袋子的物品。

那就是在枚举第 i 个袋子的时候，将所有体积小于等于 c_i 的物品放入优先队列中，然后取堆顶累加即可。

时间复杂度：枚举袋子 \Theta(K)，维护优先队列 \Theta(\log N)，总复杂度 \Theta(K\times\log N)，能水过去。

代码：

#include<cstdio>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
int n,k,now=1,ans,c[300001];
struct Things{
    int m,v;
    bool operator < (const Things &rhs) const {
        return v<rhs.v; 
    }
}a[300001];
priority_queue<Things>pq;
bool cmp(const Things &x,const Things &y){
    return x.m<y.m;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].m,&a[i].v);
    for(int i=1;i<=k;i++)
        scanf("%lld",&c[i]);
    sort(a+1,a+1+n,cmp);
    sort(c+1,c+1+k);
    for(int i=1;i<=k;i++){
        while(a[now].m<=c[i]&&now<=n)
            pq.push(a[now]),now++;
        if(pq.empty()) continue; 
        Things tmp=pq.top();pq.pop();
        ans+=tmp.v;
    }
    printf("%lld",ans);
    return 0;
}

AC！

AC 以后，我开始了良（sang）心（xin）友（bing）好（kuang）的卡常，但是发现还是卡不过 liqingyang 大佬，慢了 20 多 ms。

upd：在 lmpp 大佬的指点下，代码速度又提升了 10ms ，达到了 172ms。

代码有亿点点长，就放剪贴板里了，想学卡常的可以看看。

题解 P6538 【[COCI2013-2014#1] LOPOV】

The End.