[白俊]#1561遊園地

質問する

N人の子供が一列に並んでいて、遊園地で一人乗りのアトラクションを待っています.この遊園地にはMクラスのシングルアトラクションがあり、番号は1番からM番までです.
すべてのアトラクションにそれぞれ運行時間があり、運行時間が過ぎると乗っていた子供が降ります.アトラクションが空いている場合は、現在の列の一番前に立っている子供がアトラクションに搭乗します.複数のアトラクションが同時に空いていれば、先にもっと小さい番号が書かれたアトラクションに乗るそうです.
アトラクションが全部空いている場合、最初のお子様がアトラクションに乗る場合は、最後のお子様が乗るアトラクションの番号を求めるプログラムを作成してください.

入力

1行目では、N(1≦N≦20000000)とM(1≦M≦10000)の間にスペースがある.2行目には各アトラクションの運行時間を示すM個の自然数が順次与えられる.運行時間は1以上30以下の自然数で、単位は分です.

しゅつりょく

1行目に最後の子供が乗るアトラクションの番号を出力します.

入力例1

22 5
1 2 3 4 5

サンプル出力1

4

に答える

この問題は二分探索アルゴリズムで解決できる.1時間にアトラクションに乗れる人数をチェックし、二分探索を行います.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int M;
    static long[] times;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        times = new long[M];
        for(int i=0; i<M; i++) {
            times[i] = Integer.parseInt(input[i]);
        }

        if(N<=M) {      //놀이 기구에 한번에 다 탈 수 있는 경우
            System.out.println(N);
            return;
        }

        long left = 0;
        long right = (long)30*N;    //최대 시간

        while(left<=right) {
            long mid = (left+right)/2;
            long x = count(mid);
            long y = count(mid+1);

            if(x<N && y>=N) {      
                for(int i=0; i<M; i++) {
                    if((mid+1)/times[i] > mid/times[i])
                        x++;

                    if(x==N) {
                        System.out.println(i+1);
                        return;
                    }
                }
            }

            else if(x>=N)
                right = mid-1;

            else
                left = mid+1;
        }
    }

    public static long count(long time) {   //놀이기구 이용가능한 인원 수 구하는 메소드
        long cnt = 1;             //처음에는 모든 놀이기구가 비어있기 때문에 1를 더해줌

        for(int i=0; i<M; i++) {
            cnt += time/times[i];     //단위 시간 마다 탈 수 있기 때문에 나눠서 놀이기구에 승객이 탈 수 있는 횟수를 구한다.
        }

        return cnt;
    }
}