結果
問題 | No.68 よくある棒を切る問題 (2) |
ユーザー | Grenache |
提出日時 | 2016-07-05 19:22:24 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,436 ms / 5,000 ms |
コード長 | 2,115 bytes |
コンパイル時間 | 3,358 ms |
コンパイル使用メモリ | 80,812 KB |
実行使用メモリ | 92,612 KB |
最終ジャッジ日時 | 2024-04-20 22:05:04 |
合計ジャッジ時間 | 24,446 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,240 ms
82,976 KB |
testcase_01 | AC | 1,289 ms
82,812 KB |
testcase_02 | AC | 1,283 ms
82,656 KB |
testcase_03 | AC | 1,436 ms
92,612 KB |
testcase_04 | AC | 1,299 ms
82,964 KB |
testcase_05 | AC | 1,423 ms
81,488 KB |
testcase_06 | AC | 1,249 ms
78,064 KB |
testcase_07 | AC | 1,233 ms
81,640 KB |
testcase_08 | AC | 1,296 ms
77,312 KB |
testcase_09 | AC | 1,334 ms
79,864 KB |
ソースコード
import java.io.*; import java.util.*; public class Main_yukicoder68 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Printer pr = new Printer(System.out); int n = sc.nextInt(); // int[] l = new int[n]; PriorityQueue<Pair> pq = new PriorityQueue<>(n); for (int i = 0; i < n; i++) { // l[i] = sc.nextInt(); pq.add(new Pair(sc.nextInt(), 1)); } double[] ans = new double[500_000 + 1]; for (int i = 1; i <= 500_000; i++) { Pair e = pq.remove(); ans[i] = (double)e.a / e.b; e.b++; pq.add(e); } int q = sc.nextInt(); for (int i = 0; i < q; i++) { int k = sc.nextInt(); pr.printf("%.10f\n", ans[k]); } pr.close(); sc.close(); } private static class Pair implements Comparable<Pair> { int a; int b; Pair(int a, int b) { this.a = a; this.b = b; } @Override public int compareTo(Pair o) { double tmp1 = (double)a / b; double tmp2 = (double)o.a / o.b; if (tmp1 == tmp2) { return Integer.compare(this.b, o.b); } return Double.compare(tmp2, tmp1); } } @SuppressWarnings("unused") private static class Scanner { BufferedReader br; Iterator<String> it; Scanner (InputStream in) { br = new BufferedReader(new InputStreamReader(in)); } String next() throws RuntimeException { try { if (it == null || !it.hasNext()) { it = Arrays.asList(br.readLine().split(" ")).iterator(); } return it.next(); } catch (IOException e) { throw new IllegalStateException(); } } int nextInt() throws RuntimeException { return Integer.parseInt(next()); } long nextLong() throws RuntimeException { return Long.parseLong(next()); } float nextFloat() throws RuntimeException { return Float.parseFloat(next()); } double nextDouble() throws RuntimeException { return Double.parseDouble(next()); } void close() { try { br.close(); } catch (IOException e) { // throw new IllegalStateException(); } } } private static class Printer extends PrintWriter { Printer(PrintStream out) { super(out); } } }