#610394 (Java) No.68 よくある棒を切る問題 (2)

• 問題: No.68 よくある棒を切る問題 (2)
• ユーザー: tenten
• 提出日時: 2021-01-27 19:21:33
• 言語: Java (openjdk 23)
• 結果: WA
• 実行時間: -
• コード長: 3,456 bytes
• コンパイル時間: 2,409 ms
• コンパイル使用メモリ: 82,676 KB
• 実行使用メモリ: 110,528 KB
• 最終ジャッジ日時: 2024-06-24 21:24:03
• 合計ジャッジ時間: 29,732 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
other	WA * 10

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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;
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX