题解 SP16409 【LOPOV - Lopov】

很简单的一个贪心，就是在背包容量内的物品尽量塞价值大的。 具体做法就是，把背包和物品都按容量排一个序，然后弄两个指针i和j，O(n)扫一遍，对于每一个背包，就塞进去比它容量小且没被选过的物品价值最大的，用优先队列就可以维护了。 ``` #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; int n,m; int c[300100],f[300100]; struct Book { int w,v,f; }b[300100]; priority_queue <int> q; bool cmp1(Book x,Book y) {return x.w==y.w?x.v<y.v:x.w<y.w;} int read() { int x=0,flag=0; char ch=getchar(); if(ch=='-') flag=1; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); if(flag) return -x; return x; } signed main() { n=read(),m=read(); for(int i=1;i<=n;i++) b[i].w=read(),b[i].v=read(); for(int i=1;i<=m;i++) c[i]=read(); sort(b+1,b+n+1,cmp1); sort(c+1,c+m+1); int j=1,ans=0;b[n+1].w=0x7fffffff; for(int i=1;i<=n+1;i++) { while(b[i].w>c[j])//当前物品容量比背包大了，就把优先队列里面的物品往背包里面塞 { if(!q.empty()) ans+=q.top(),q.pop(); j++;if(j>m) break; } if(j>m) break; q.push(b[i].v); } printf("%lld",ans); return 0; } ```