Codeforce 140C （贪心+优先队列）补题
C. New Year Snowmen time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output As meticulous Gerald sets the table and caring Alexander sends the postcards, Sergey makes snowmen. Each showman should consist of three snowballs: a big one, a medium one and a small one. Sergey’s twins help him: they’ve already made n snowballs with radii equal to r1, r2, …, rn. To make a snowman, one needs any three snowballs whose radii are pairwise different. For example, the balls with radii 1, 2 and 3 can be used to make a snowman but 2, 2, 3 or 2, 2, 2 cannot. Help Sergey and his twins to determine what maximum number of snowmen they can make from those snowballs.
Input The first line contains integer n (1 ≤ n ≤ 105) — the number of snowballs. The next line contains n integers — the balls’ radii r1, r2, …, rn (1 ≤ ri ≤ 109). The balls’ radii can coincide.
Output Print on the first line a single number k — the maximum number of the snowmen. Next k lines should contain the snowmen’s descriptions. The description of each snowman should consist of three space-separated numbers — the big ball’s radius, the medium ball’s radius and the small ball’s radius. It is allowed to print the snowmen in any order. If there are several solutions, print any of them.
Examples inputCopy 7 1 2 3 4 5 6 7 outputCopy 2 3 2 1 6 5 4 inputCopy 3 2 2 3 outputCopy 0
一开始想暴力，奈何10^9过不了，这是有贪心策略的，既然要使的堆成雪人的数量最多，比如 6 3 3 3 2 2 2 2 1 1，要想使的雪人数量最多，应该尽可能的让2 分到更多组，但是每个雪球只能用一次，当2用的比3少的时候，应该改优先为3，所以应该写一个结构体，先按照数量排序，再按半径排序，每次拿前三个即可。 尴尬：取完一定要放回去，还要是数量减一。
#include <bits/stdc++.h>
using namespace std;
struct Node{
int arr,num; //半径，数目
}node[100005];
map <int,int> M;
priority_queue <Node> Q; //默认大根队列，先出队列的为最大的
vector <int> V[3];
bool operator < (Node a,Node b){
return a.num < b.num;
}
int main()
{
int n;
while(~scanf("%d",&n)){
while(!Q.empty())
Q.pop();
M.clear();
for(int i = 0;i < 3;i ++) V[i].clear();
int temp;
for(int i = 1;i <= n;i ++){
scanf("%d",&temp)
M[temp]++;
}
int len = 0;
map <int,int>::iterator it;
for(it = M.begin();it != M.end();it ++){ //结构体存半径和数目
node[len].arr = it->first;
node[len++].num = it->second;
}
for(int i = 0;i < len;i ++) //入队列
Q.push(node[i]);
len = 0;
while(!Q.empty()){
Node res1 = Q.top();
Q.pop();
if(Q.empty()) break;
Node res2 = Q.top();
Q.pop();
if(Q.empty()) break;
Node res3 = Q.top();
Q.pop();
int temp[3] = {res1.arr,res2.arr,res3.arr};
sort(temp,temp+3);
V[0].push_back(temp[2]);
V[1].push_back(temp[1]);
V[2].push_back(temp[0]);
res1.num--,res2.num--,res3.num--;
if(res1.num) Q.push(res1); //数目不为0时继续入队列
if(res2.num) Q.push(res2);
if(res3.num) Q.push(res3);
}
cout<<V[0].size()<<endl;
for(int i = 0;i < V[0].size();i ++)
cout<<V[0][i]<<" "<<V[1][i]<<" "<<V[2][i]<<endl;
}
return 0;
}腾讯云开发者
