LOPOV 题解

· · 题解

难度：黄

做法：贪心

定义：C_{k}为第k个袋子的容量，M_{i}为第i个物品的质量，V_{i}是第i个物品的价值，袋子总数为m，物品总数为n

推导一：对于当前要装入袋子中的物品i，要装入C_{k}，如果有C_{t}满足M_{i}\leq C_{t}<C_{k}，则把i物品装入t袋子更优；如果有物品j满足V_{j}>V_{i}且M_{j}\leq C_{k}，则选j更优

对于两个V相等的值，需要先装M小的嘛？

显然是不需要的，假设当前两个值有不是最优解的，那么可以找到一个比它更优的解来替代。直至物品i,j都是袋子k最优解时，假设V_{i}=V_{j}且M_{i}<M_{j}。若最优解有i,j两个数（相对有k），则说明有两个袋子能够装下这两个物品，所以无需比较其M的大小；若最优解只包含其中一个，则k装的物品它产生的价值恒为V，所以不需要比较大小，如果都装不下，就违背了最优解的说法，所以不成立。

根据推导一，我们可以发现，对于当前解i，保证没有满足V_{j}>V_{i}的j就可以把它放进一个容量为C_{k}的袋子，并且不存在有M_{i}<C_{t}<C_{k}

我们考虑先按照V从大到小排序（手动保证当前操作的数i没有j满足V_{j}>V_{i}），对于当前物品，找到一个k满足不存在有M_{i}<C_{t}<C_{k}，即找到M_{i}的后继

我们可以维护Set/平衡树(因为Set好写所以就写Set了)

先讲袋子容量插入Set，再按照V讲物品排序，然后对于当前物品i，在Set中查找第一个质量大于等于M_{i}的袋子，如果有则删除次袋子并把V_{i}加入最终结果，没有的话就继续查找下一个袋子。

附代码：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int maxn(3e5+5);
long long n,m,x;
long long ans=0;
struct node{ int w,v; }a[maxn];
multiset <int> s;
int read(){
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool cmp(node x,node y){ return x.v>y.v; }
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i].w=read(),a[i].v=read();
    for(int i=1;i<=m;i++) x=read(),s.insert(x);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        multiset<int>::iterator k=s.lower_bound(a[i].w);
        if(k!=s.end()) s.erase(k),ans+=a[i].v;  
    }
    printf("%lld\n",ans);
    return 0;
}

总结：这道题实现上还是比较水的，学贪心的朋友可以练练手，学平衡树和Stl朋友也可以写写代码，祝各位AC

（请不要帮助小偷！）