牛客--最小化价格

xiaoxiao2021-02-28  7

题意: 点击打开链 题意: 现有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; }
转载请注明原文地址: https://www.6miu.com/read-2000128.html

最新回复(0)