結果

問題 No.120 傾向と対策：門松列（その１）
ユーザー hanorverhanorver
提出日時 2016-05-24 13:53:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 60 ms / 5,000 ms
コード長 1,214 bytes
コンパイル時間 999 ms
コンパイル使用メモリ 89,928 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 05:08:22
合計ジャッジ時間 2,123 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
5,248 KB
testcase_01 AC 60 ms
5,248 KB
testcase_02 AC 31 ms
5,248 KB
testcase_03 AC 60 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>

bool isBambooCol(int a, int b, int c) {
	// a,b,cが門松列かの判定
	if (a == b || a == c || b == c) return false;
	if (b < a && b < c) return true;
	if (b > a && b > c) return true;
	return false;
}

void calc() {
	int bamboo_no; // 竹の本数
	std::cin >> bamboo_no;

	// <個数, 竹の長さ>
	std::priority_queue<std::pair<int, int> > bamboo;
	std::map<int, int> m;
	for (int i = 0; i < bamboo_no; i++) {
		int bamboo_length;
		std::cin >> bamboo_length;
		m[bamboo_length]++;
	}

	for (auto it = m.begin(); it != m.end(); it++) {
		bamboo.push({ it->second, it->first });
	}


	long long ans = 0;
	while (!bamboo.empty()) {
		auto f = bamboo.top(); bamboo.pop();
		if (bamboo.empty()) break;
		auto s = bamboo.top(); bamboo.pop();
		if (bamboo.empty()) break;
		auto t = bamboo.top(); bamboo.pop();

		ans++;
		f.first--;
		s.first--;
		t.first--;

		if(f.first != 0) bamboo.push(f);
		if(s.first != 0) bamboo.push(s);
		if(t.first != 0) bamboo.push(t);
	}

	std::cout << ans << std::endl;
}


int main() {
	int test_case;
	std::cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		calc();
	}

	return 0;
}
0