結果

問題 No.120 傾向と対策：門松列（その１）
ユーザー mitsuomitsuo
提出日時 2016-05-15 22:48:02
言語 Java21
(openjdk 21)
結果
AC  
実行時間 736 ms / 5,000 ms
コード長 1,564 bytes
コンパイル時間 2,427 ms
コンパイル使用メモリ 89,324 KB
実行使用メモリ 49,492 KB
最終ジャッジ日時 2024-04-15 22:14:55
合計ジャッジ時間 6,250 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 736 ms
49,492 KB
testcase_01 AC 715 ms
48,632 KB
testcase_02 AC 563 ms
48,440 KB
testcase_03 AC 726 ms
48,680 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package jp.fedom.challange.yuki.l2.q120;

import java.io.ByteArrayInputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class CN {
	public CN(long l, int i) {
		T = l;
		n = i;
	}

	long T;
	int n;

	public String toString() {
		return T + "/" + n;
	}

}

public class Main {

	public static void main(String[] args) {
		Scanner sc;
		if (args.length == 0) {
			sc = new Scanner(System.in);
		} else {
			sc = new Scanner(new ByteArrayInputStream(args[0].getBytes()));
		}
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			int N = sc.nextInt();
			long[] L = new long[N];
			for (int j = 0; j < N; j++) {
				L[j] = sc.nextLong();
			}
			System.out.println(solve(N, L));
		}
		sc.close();
	}

	public static int solve(int N, long[] L) {
		Map<Long, CN> nm = new HashMap<>();
		for (long l : L) {
			if (!nm.containsKey(l)) {
				nm.put(l, new CN(l, 0));
			}
			nm.get(l).n++;
		}
		Queue<CN> qu = new PriorityQueue<>(new Comparator<CN>() {
			@Override
			public int compare(CN o1, CN o2) {
				return o2.n - o1.n;
			}
		});
		qu.addAll(nm.values());

		int c = 0;
		while (qu.size() >= 3) {
			CN cn1 = qu.poll();
			CN cn2 = qu.poll();
			CN cn3 = qu.poll();
			cn1.n--;
			cn2.n--;
			cn3.n--;
			c++;
			if (cn1.n > 0) {
				qu.add(cn1);
			}
			if (cn2.n > 0) {
				qu.add(cn2);
			}
			if (cn3.n > 0) {
				qu.add(cn3);
			}
		}

		return c;
	}
}
0