結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー threepipes_sthreepipes_s
提出日時 2014-11-17 02:02:52
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 1,860 bytes
コンパイル時間 2,244 ms
コンパイル使用メモリ 87,280 KB
実行使用メモリ 78,236 KB
最終ジャッジ日時 2024-06-10 09:20:30
合計ジャッジ時間 15,229 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
public class Main {
	public static List<Long> k = new ArrayList<Long>();
	public static HashMap<Long, Double> lens = new HashMap<Long, Double>();
	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(" ");
			double[] l = new double[n];
//			double[] k = new double[q];
			
			for(int i=0; i<n; i++){
				l[i] = Double.parseDouble(tmp0[i]);
			}
			for(int i=0; i<q; i++){
				long newk =  Long.parseLong(tmp1[i]);
				int idx = Collections.binarySearch(k, newk);
				double min = 0;
				double max = 1e9;
				if(k.size() == 0){
					k.add(newk);
				}else if(idx < 0){
					max = lens.get(k.get(0));
					k.add(0, newk);
				}else if(idx >= k.size()){
					min = lens.get(k.get(k.size()-1));
					k.add(newk);
				}else{
					min = lens.get(k.get(idx-1));
					max = lens.get(k.get(idx));
					k.add(idx, newk);
				}
				double len = getLen(l, n, newk, min, max);
				System.out.println(len);
				lens.put(newk, len);
			}
		}catch(IOException e){
			e.printStackTrace();
		}
	}
	
	public static double getLen(double[] l, int n, double k, double min, double max){
		double len = 0;
		long cut;
		while(max - min > 1e-9){
			len = (min+max)/2.0;
			cut = 0;
			for(int j=0; j<n; j++){
				cut += (long)(l[j]/len);
			}
			if(cut < k){
				max = len;
			}else{
				min = len;
			}
		}
		return len;
	}

}
0