結果

問題 No.275 中央値を求めよ
コンテスト
ユーザー shinwisteria
提出日時 2017-03-18 19:31:02
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,300 bytes
コンパイル時間 3,303 ms
コンパイル使用メモリ 78,360 KB
実行使用メモリ 41,692 KB
最終ジャッジ日時 2024-07-04 19:20:16
合計ジャッジ時間 6,635 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;

public class Median {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		int[] A = new int[N];
		for(int i = 0;i < N ;i++){
			A[i] = s.nextInt();
		}
		s.close();
		quicksort Q = new quicksort();
		A = Q.quick(A);

		double med = 0;
		if(N % 2 == 1){
			med = (double)A[(N-1)/2];
		}else{
			med = (double)(A[N/2-1] + A[N/2]) /2;
		}
		System.out.println(String.format("%.1f",med));
	}

}

class quicksort {
	public int[] quick(int[] d){
		int med = (d[0] + d[d.length-1]) / 2;
		int[] mm = new int[2];
		mm = maxmin(d);
		if(mm[0] == mm[1]){
		}else{
			int count = 0;
			for(int i = 0;i < d.length;i++){
				if(d[i] <= med){
					count++;
				}
			}
			int[] d1 = new int[count];
			int[] d2 = new int[d.length - count];
			int d1count = 0,d2count = 0;
			for(int i = 0;i < d.length;i++){
				if(d[i] <= med){
					d1[d1count++] = d[i];
				}else{
					d2[d2count++] = d[i];
				}
			}
			d1 = quick(d1);
			d2 = quick(d2);
			int k = 0;
			for(int n : d1){
				d[k++] = n;
			}
			for(int n : d2){
				d[k++] = n;
			}
		}
		return d;
	}
	
	static int[] maxmin(int[] d){
		int[] mm = {d[0] ,d[0]};
		for(int n : d){
			if(n < mm[0]){
				mm[0] = n;
			}else if(n > mm[1]){
				mm[1] = n;
			}
		}
		return mm;
	}
}
0