题解 P6538 【[COCI2013-2014#1] LOPOV】
MC_Launcher · · 题解
两周没发题解了，来水一篇题解
题意:给你k个袋子,n个物品，分别有价值
很明显这玩意是贪心的策略，我先给大家提供一下思路：
先将袋子和物品从小到大排个序（物品按质量排），接着便利每个袋子，每次便利将能够装下都记录，找到最大的那个并标记。
给一个简单的证明（大佬勿喷）：
假如任意两个袋子所装的物品价值与重量都不同，那么每个袋子装的必定是其能装下的最大值，成立
假如两个袋子可以装重量相同的物品，那么用小的袋子装这个物品可以使大的袋子装更重的物品，可能价值会更高
那么怎么实现呢？暴力？
NO，NO，NO，暴搜复杂度
所以我们用一个优先队列(priority_queue)来实现
上代码
#include<bits/stdc++.h>
using namespace std;
struct thing//物品
{
int m;//质量;
int v;//价值
};
bool pai(thing a,thing b)
{
return a.m<b.m;//定义thing结构体排序方式，按物品质量排序
}
bool operator<(thing a,thing b)//重载thing结构体"<"运算符，按价值排
{
return a.v<b.v;
}
priority_queue<thing>que;
thing th[300002];//所有物品
int bag[300002];//所有袋子
int main()
{
int n,k;//物品数量，袋子数量
cin>>n>>k;//输入物品数量和袋子数量
long long ans=0;//记录答案
for(int i=0;i<n;i++)
{
cin>>th[i].m>>th[i].v;//获取物品质量和价值
}
for(int i=0;i<k;i++)
{
cin>>bag[i];//获取袋子容量
}
sort(th,th+n,pai);//将物品按重量从小到大排序
sort(bag,bag+k);//将袋子容量从小到大排序
int weizhi=0;//记录当前进队到第几个物品
for(int i=0;i<k;i++)//便利每个袋子
{
for(int j=weizhi;j<n;j++)//从上次入队的物品开始继续便利
{
if(th[j].m<=bag[i])//如果能装下，则装进队列
{
que.push(th[j]);
weizhi++;//记录入队到第几个物品了
}
else//装不下？由于按质量排序，所以接下来的也不行
{
break;
}
}
if(!que.empty())
{
ans+=que.top().v;//记录价值
que.pop();//出队
}
}
cout<<ans;
}