結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー threepipes_sthreepipes_s
提出日時 2014-11-17 03:35:52
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,256 ms / 5,000 ms
コード長 1,839 bytes
コンパイル時間 2,400 ms
コンパイル使用メモリ 78,136 KB
実行使用メモリ 82,084 KB
最終ジャッジ日時 2024-06-10 19:49:40
合計ジャッジ時間 21,911 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,147 ms
79,464 KB
testcase_01 AC 1,139 ms
79,588 KB
testcase_02 AC 1,148 ms
79,132 KB
testcase_03 AC 1,211 ms
82,040 KB
testcase_04 AC 1,206 ms
81,804 KB
testcase_05 AC 1,256 ms
82,084 KB
testcase_06 AC 1,094 ms
76,964 KB
testcase_07 AC 1,108 ms
78,836 KB
testcase_08 AC 1,122 ms
78,968 KB
testcase_09 AC 1,111 ms
79,252 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>(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