题意:
点击打开链
题意:
现有n组人,m个地点,给出每组人的人数,每个地点可容纳的最大人数和选择的价格,要求一种方式,使得每组人都到一个各不相同的地点,最小化选择的价格 。每个队伍的人都要在同一个地方每个地方只能有一个队伍
思路:n组从大到小,把能装下当前组的地点价格放进multiset,(注意价格可能重,所以不能set)每次都取最优的,价钱最小的,
感想:这是第一次,完全靠自己想到用set,进而想到multiset。感觉还不错。以后对这种顺序有关的感觉会越来越敏感的!
代码:
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f;
int n,a[100500],m;
long long ans;
struct AA
{
int num,p;
}pos[100005];
bool cmp(AA aa,AA bb)
{
return aa.num>bb.num;
}
int main()
{
ans=0;
multiset<int>q;
multiset<int>::iterator it;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int j=1;j<=m;j++)
{
scanf("%d%d",&pos[j].num,&pos[j].p);
}
sort(pos+1,pos+m+1,cmp);
int l,j=1;
for(int i=n;i>=1;i--)
{
while(1)
{
if(j<=m&&pos[j].num>=a[i])
{
q.insert(pos[j].p);
j++;
}
else break;
}
//cout<<q.size()<<endl;
if(q.empty()){ans=-1;break;}
else
{
it=q.begin();
q.erase(it);
ans+=*it;
}
//cout<<i<<" "<<j<<endl;
}
cout<<ans<<endl;
}