結果

問題 No.2453 Seat Allocation
ユーザー AsahiAsahi
提出日時 2023-09-01 22:52:25
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,705 ms / 2,000 ms
コード長 1,725 bytes
コンパイル時間 2,621 ms
コンパイル使用メモリ 80,440 KB
実行使用メモリ 65,752 KB
最終ジャッジ日時 2024-06-25 09:31:03
合計ジャッジ時間 27,449 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int[] A = new int[N];
        int[] B = new int[M];
        
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        
        for (int i = 0; i < M; i++) {
            B[i] = sc.nextInt();
        }
        
        PriorityQueue<Candidate> pq = new PriorityQueue<>();
        
        for (int i = 0; i < N; i++) {
            pq.add(new Candidate(A[i], B[0], i + 1, 0));
        }
        
        for (int i = 0; i < M; i++) {
            Candidate winner = pq.poll();
            System.out.println(winner.party);
            
            int nextIndex = winner.index + 1;
            if (nextIndex < M) {
                pq.add(new Candidate(A[winner.party - 1], B[nextIndex], winner.party, nextIndex));
            }
        }
    }
    
    static class Candidate implements Comparable<Candidate> {
        int numerator;
        int denominator;
        int party;
        int index;
        
        Candidate(int numerator, int denominator, int party, int index) {
            this.numerator = numerator;
            this.denominator = denominator;
            this.party = party;
            this.index = index;
        }
        
        @Override
        public int compareTo(Candidate o) {
            long x = (long) this.numerator * o.denominator;
            long y = (long) o.numerator * this.denominator;
            if (x != y) {
                return Long.compare(y, x);
            }
            return Integer.compare(this.party, o.party);
        }
    }
}
0