CF140CNew Year Snowmen

CF140C

题目大意:堆雪人,需要三个大小不同的雪球,现有\(n\)个给定大小的雪球，问最多堆多少个雪人

一个很明显的思路是把每种雪球出现的个数记录下来,然后直接扔到大根堆里面,每次选择剩下出现次数最多的三个堆成一个雪人,可以证明,这样一定不会比选择小的更劣

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 2e5 + 3;

int a[N];

int n;

int s[5];

priority_queue <pii> q;

struct node{

	int x,y,z;

}qq[N];

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

int main(){

	n = read();

	for(int i = 1;i <= n;++i) a[i] = read();

	sort(a + 1,a + n + 1);

	int res = 1;

	for(int i = 1;i <= n;++i){

		if(a[i] == a[i + 1]) res++;

		else{

			q.push(mk(res,a[i]));

			res = 1;

		}

	}int ans = 0;

	while(q.size() >= 3){

		pii k1 = q.top();q.pop();

		pii k2 = q.top();q.pop();

		pii k3 = q.top();q.pop();

		ans++;

		s[1] = k1.se,s[2] = k2.se,s[3] = k3.se;

		sort(s + 1,s + 4);

		qq[ans] = (node){s[3],s[2],s[1]};

		k1.fi--,k2.fi--,k3.fi--;

		if(k1.fi) q.push(k1);

		if(k2.fi) q.push(k2);

		if(k3.fi) q.push(k3);

	}

	printf("%d\n",ans);

	for(int i = 1;i <= ans;++i) printf("%d %d %d\n",qq[i].x,qq[i].y,qq[i].z);

    return 0;

}

巴特西

CF140CNew Year Snowmen

CF140C

最新文章

热门文章