結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー threepipes_sthreepipes_s
提出日時 2014-11-17 03:37:30
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,201 ms / 5,000 ms
コード長 1,842 bytes
コンパイル時間 2,080 ms
コンパイル使用メモリ 74,652 KB
実行使用メモリ 95,300 KB
最終ジャッジ日時 2023-08-30 20:19:40
合計ジャッジ時間 21,091 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,113 ms
91,160 KB
testcase_01 AC 1,124 ms
91,844 KB
testcase_02 AC 1,103 ms
91,236 KB
testcase_03 AC 1,128 ms
95,300 KB
testcase_04 AC 1,170 ms
92,168 KB
testcase_05 AC 1,201 ms
95,248 KB
testcase_06 AC 1,045 ms
88,400 KB
testcase_07 AC 1,048 ms
89,136 KB
testcase_08 AC 1,069 ms
88,356 KB
testcase_09 AC 1,068 ms
89,220 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
//	public static List<Long> k = new ArrayList<Long>();
	public static PriorityQueue<Pair> lens = new PriorityQueue<Pair>(1, new MyComparator());
//	public static HashMap<Long, Integer> cutNum = new HashMap<Long, Integer>();
	public static int maxK = (int) 5e5;
	public static void main(String[] args){
		BufferedReader input
		= new BufferedReader(new InputStreamReader(System.in));
		try{
			int n = Integer.parseInt(input.readLine().trim());
			String tmp0[] = input.readLine().trim().split(" ");
			int q = Integer.parseInt(input.readLine().trim());
			String tmp1[] = input.readLine().trim().split(" ");
			int[] cutNum = new int[q];
			double[] res = new double[maxK];
			double[] len = new double[n];
			
			for(int i=0; i<n; i++){
				len[i] = Double.parseDouble(tmp0[i]);
				Pair p = new Pair(len[i], i);
				lens.add(p);
			}
			for(int i=0; i<q; i++){
				cutNum[i] = 0;
			}
			for(int i=0; i<maxK; i++){
				Pair p = lens.poll();
				res[i] = p.d;
				lens.add(new Pair(len[p.i]/(++cutNum[p.i]+1), p.i));
			}
			for(int i=0; i<q; i++){
				System.out.println(res[Integer.parseInt(tmp1[i])-1]);
			}
		}catch(IOException e){
			e.printStackTrace();
		}
	}
}

class Pair{
	double d;
	int i;
	public Pair(double d, int i){
		this.d = d;
		this.i = i;
	}
}

class MyComparator implements Comparator<Pair> {
	 
    public int compare(Pair obj1, Pair obj2) {
         
        Pair p1 = obj1;
        Pair p2 = obj2;
         
        if(p1.d < p2.d) {
            return 1;
        } else if(p1.d > p2.d) {
            return -1;
        } else{
            return 0;
        }
 
    }
 
}
0