Codeforces Round #100 C : New Year Snowmen

問題概要

長さN(<10^5)の整数列が与えられる。互いにことなる3つを選んでひとつのグループを構成することができる。最大でいくつのグループができるかを求め、実際に復元する問題。

解法

いくつできるかを二分探索で求め、その答えを利用して復元すれば良い。heapを使ってgreedyにやってもできるらしい(計算量は多分一緒？かしこいheap使えば計算量落ちるかも)

acceptされたコード

計算量O(N * log N)。以下の実装はmapを直接使ってるのでさらにlogがかかる。

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

const int MAX_N = 1e5;

int N;
int as[MAX_N];
int xs[MAX_N][3];

map<int, int> dict;

bool check(int x){

	int cnt = 0;
	for(map<int,int>::iterator itr=dict.begin(); itr!=dict.end(); itr++){
		cnt += min(x, itr->second);
	}

	return cnt >= 3*x;
}

void solve(){
	sort(as, as + N);

	for(int i=0; i<N; i++){
		dict[as[i]]++;
	}

	int low = 0, high = N;
	while(high - low > 1){
		int mid = (high + low) / 2;
		if(check(mid)){
			low = mid;
		}
		else{
			high = mid;
		}
	}

	int ans = low;
	printf("%d\n", low);

	map<int,int> use;

	int p = 0, q = 0;
	for(int i=0; i<N; i++){
		if(use[as[i]] < ans){
			use[as[i]]++;
			xs[p++][q] = as[i];
			if(p==ans){
				q++;
				p = 0;
				if(q == 3){
					break;
				}
			}
		}
	}

	for(int i=0; i<ans; i++){
		sort(xs[i], xs[i]+3);
		printf("%d %d %d\n", xs[i][2], xs[i][1], xs[i][0]);
	}
}

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", as+i);
	}
	solve();

	return 0;
}