結果

問題 No.68 よくある棒を切る問題 (2)
コンテスト
ユーザー tenten
提出日時 2021-01-27 19:21:33
言語 Java
(openjdk 25.0.1)
結果
WA  
実行時間 -
コード長 3,456 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,409 ms
コンパイル使用メモリ 82,676 KB
実行使用メモリ 110,528 KB
最終ジャッジ日時 2024-06-24 21:24:03
合計ジャッジ時間 29,732 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        TreeSet<Stick> sticks = new TreeSet<>();
        TreeSet<Stick> nexts = new TreeSet<Stick>(new Comparator<Stick>() {
            public int compare(Stick s1, Stick s2) {
                if (s1.idx == s2.idx) {
                    return 0;
                } else {
                    double diff = s1.value / s1.count  - s2.value / s2.count;
                    if (diff == 0) {
                        return s1.idx - s2.idx;
                    } else if (diff < 0) {
                        return -1;
                    } else {
                        return 1;
                    }
                }
            }
        });
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            Stick s = new Stick(i, arr[i]);
            sticks.add(s);
            nexts.add(s);
        }
        Arrays.sort(arr);
        int q = sc.nextInt();
        Question[] questions = new Question[q];
        for (int i = 0; i < q; i++) {
            questions[i] = new Question(i, sc.nextInt());
        }
        Arrays.sort(questions);
        double[] ans = new double[q];
        int count = n;
        for (int i = 0; i < q; i++) {
            if (questions[i].value <= n) {
                ans[questions[i].idx] = arr[n - questions[i].value];
            } else {
                while (count < questions[i].value) {
                    Stick s = sticks.pollLast();
                    nexts.remove(s);
                    s.add();
                    sticks.add(s);
                    nexts.add(s);
                    count++;
                }
                ans[questions[i].idx] = nexts.first().getValue();
            }
        }
        StringBuilder sb = new StringBuilder();
        for (double x : ans) {
            sb.append(x).append("\n");
        }
        System.out.print(sb);
    }
    
    static class Stick implements Comparable<Stick> {
        int idx;
        double value;
        int count = 1;
        
        public Stick(int idx, double value) {
            this.idx = idx;
            this.value = value;
        }
        
        public int hashCode() {
            return idx;
        }
        
        public boolean equals(Object o) {
            Stick s = (Stick)o;
            return idx == s.idx;
        }
        
        public int compareTo(Stick another) {
            if (idx == another.idx) {
                return 0;
            } else {
                double diff = value / (count + 1)  - another.value / (another.count + 1);
                if (diff == 0) {
                    return idx - another.idx;
                } else if (diff < 0) {
                    return -1;
                } else {
                    return 1;
                }
            }
        }
        
        public double getValue() {
            return value / count;
        }
        
        public void add() {
            count++;
        }
    }
    
    static class Question implements Comparable<Question> {
        int idx;
        int value;
        
        public Question(int idx, int value) {
            this.idx = idx;
            this.value = value;
        }
        
        public int compareTo(Question another) {
            return value - another.value;
        }
    }
}
0