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

· · 题解

这题的贪心做法很好想，相信大家都猜到了。

分析题目

贪心做法：

step 1:把物品从大到小进行排序；

step2:循环每个物品，找到背包容量 \ge 这个物品的体积的背包中容量最小的背包并删除它，同时将总价值加上这个物品的价值。

证明： 对于 step 1 ，因为我们希望取到的总价值最大，所以价值大的肯定要先拿。

对于 step 2 ，因为我们要“勤俭持家”，为之后的物品留下更多空间

代码实现

用 std::multiset 实现维护背包

#include<bits/stdc++.h>
#define msii multiset<int>::iterator
using namespace std;
const int maxn=300004;
int n,k;
long long res;
struct node{
    int m,v;
    bool operator < (const node &a){
        return v>a.v;
    }
}s[maxn];
multiset < int > c;

int read(){
    char f=0,c=getchar();int ret=0;
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-')
            f=1;
    for(;c>='0'&&c<='9';c=getchar())
        ret=(ret<<1)+(ret<<3)+(c^48);
    return f?-ret:ret;
}

int main(){
    n=read(),k=read();
    for(int i=0;i<n;i++)
        s[i].m=read(),s[i].v=read();
    sort(s,s+n);    
    for(int i=0;i<k;i++)
        c.insert(read());
    for(int i=0;i<n&&k>0;i++){
        msii it=c.lower_bound(s[i].m);
        if(it!=c.end()){
            --k;
            res+=s[i].v;
            c.erase(it);
        }
    }
    printf("%lld",res);
    return 0;
}