题目链接：codeforces.com/contest/1183/problem/G
题意：使得礼物中糖果的数量不相同，让礼物中糖果总数目最大，让想送出的糖果数目最多。数目多的糖果可以作为数目少的糖果送出去。就是让数量相同的不同种类的糖果中，f=1最多的送出去，剩下的数量先减1，作为下一种数量相比较。
思路：先统计不同种糖果的总数量和f=1的数量，然后作为结构体放入优先队列，优先队列按照数量从大到小排序，数量相同的按照f=1的数量从大到小排序，设置变量记录当前已经作为礼物的数量flag，如果从队列中拿出的总数量和flag相同，就让数量-1，如果总数量和f=1的数量相同，就同时-1，然后再放入队列中。
运用优先队列有一个好处，就是可以把数据拿出来再放进去能自动排序，就这减少了很多操作。而本题用的map也可以用数组，不过map比较节省空间。
AC代码
#include<iostream> #include<queue> #include<map> #include<vector> using namespace std; const int MAX=2e5+10; struct node{ int numA,numF; bool operator <(const node &n) const { if(this->numA==n.numA)return this->numF<n.numF; else return this->numA<n.numA; } }; priority_queue<node,vector<node> >qu; map<int,int>maps,map1; int main() { int q; cin>>q; while(q--) { int n; cin>>n; int aa,f; for(int i=0;i<n;i++) { cin>>aa>>f; maps[aa]++; map1[aa]+=f; } map<int,int>::iterator it; for(it=maps.begin();it!=maps.end();it++) { node now={it->second,map1[it->first]}; qu.push(now); } int flag=-1; int ans1=0,ans2=0; while(1) { if(qu.empty()||flag==0)break; int sum=qu.top().numA; int cnt=qu.top().numF; qu.pop(); if(flag!=sum) { flag=sum; ans1+=sum; ans2+=cnt; }else{ if(sum==cnt) { sum--; cnt--; }else sum--; qu.push({sum,cnt}); } } while(!qu.empty())qu.pop(); maps.clear(); map1.clear(); cout<<ans1<<" "<<ans2<<endl; } return 0; }
Candy Box (hard version) 运用优先队列和map
原文：https://www.cnblogs.com/xlbfxx/p/11269406.html