結果

問題 No.68 よくある棒を切る問題 (2)
コンテスト
ユーザー threepipes_s
提出日時 2014-11-17 03:35:52
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,246 ms / 5,000 ms
コード長 1,839 bytes
コンパイル時間 3,386 ms
コンパイル使用メモリ 81,284 KB
実行使用メモリ 88,636 KB
最終ジャッジ日時 2025-01-02 16:26:38
合計ジャッジ時間 23,281 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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