CF140C New Year Snowmen

题目

CF140C New Year Snowmen

给 (n) 个雪球，每次从中选出三个半径严格递增的雪球做成雪人，求最多能做多少个。

分析

最开始十分 (naive) 地想分成三组来做，然后其实发现只要是选了三个不同种类的，总是可以做一个雪人。

于是考虑贪心，先把尽可能多的选掉同一类雪球最多的种类。

于是用一个堆来维护当前的雪球个数最多的种类，每次取出堆顶的三种，做一个雪人然后放回去。

显然是正确的。

代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool f=false;char ch=getchar();
	while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template<typename T>
inline void write(T x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
const int N=1e5+5;
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
int n;
unordered_map<int,int>Map;
priority_queue<PII>pq;
struct node{
	int x,y,z;
}Ans[N];
signed main(){
	read(n);int cnt=0;
	for(register int i=1,x;i<=n;i++) read(x),Map[x]++;
	for(unordered_map<int,int>::iterator it=Map.begin();it!=Map.end();it++) pq.push(mp((*it).se,(*it).first));
	while(pq.size()>=3){
		PII a,b,c;int t[4];
		a=pq.top();pq.pop();b=pq.top();pq.pop();c=pq.top();pq.pop();
		t[1]=a.se,t[2]=b.se,t[3]=c.se;
		sort(t+1,t+4);
		Ans[++cnt].x=t[3],Ans[cnt].y=t[2],Ans[cnt].z=t[1];
		a.fi--,b.fi--,c.fi--;
		if(a.fi) pq.push(a);
		if(b.fi) pq.push(b);
		if(c.fi) pq.push(c);
	}
	write(cnt),putchar('
');
	for(register int i=1;i<=cnt;i++) write(Ans[i].x),putchar(' '),write(Ans[i].y),putchar(' '),write(Ans[i].z),putchar('
');
	return 0;
}