演習課題「素数判定をおこなう」
paiza ビルにあるエスカレーターは全長 K メートルあり、 1 秒で 1 メートル進みます。また paiza ビルに勤める社員が N 人おり、 i 番目の社員は時刻 A_i にエスカレーターに乗ります。各社員がエスカレーターに乗った直後に、エスカレーター上にいる人数をそれぞれ答えてください。ただしある時刻にエスカレーターに乗る社員と降りる社員がいた場合、これは同時におこなわれます。
この問題は少し難しいですが、キューを用いて実装してみましょう。なお、サンプル 1 のケースでは以下のように社員がエスカレーターに乗ります。
入力される値
N K
A_1 ... A_N
条件
すべてのテストケースにおいて、以下の条件をみたします。
・ N, A_i は 1 以上 50,000 未満
・ 1 ≦ A_1 < ... < A_N < 50,000
・ K は 1 以上 100 未満
期待する出力
社員 i がエスカレーターに乗った直後に、エスカレーター上にいる人数 E_i を改行区切りで出力してください。末尾には改行を入れ、余計な文字、空行を含んではいけません。
E_1
...
E_N
期待する出力値
1
2
2
2
＃06:キューの活用例
このチャプターでは、キューの活用例について学習します。
paiza のレベルアップ問題集にもキューを使って解く問題がいくつかあります。
スタック・キュー問題集で練習すると良いでしょう。
https://paiza.jp/works/mondai/stack_queue
キューは幅優先探索を行う際によく登場します。
深さ優先・幅優先探索問題集という問題集があるので、ぜひ覗いてみてください。
https://paiza.jp/works/mondai/bfs_dfs_problems
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int length = 5;
Queue<Integer> que = new ArrayDeque<>();
int person_on_escalator = 0;
for (int time = 1; time < 10; time++) {
if (time == 1) {
que.add(2);
person_on_escalator += 2;
} else if (time == 3) {
que.add(5);
person_on_escalator += 5;
} else if (time == 7) {
que.add(2);
person_on_escalator += 2;
} else{
que.add(0);
}
if (que.size() > length) {
person_on_escalator -= que.poll();
}
System.out.println(person_on_escalator);
}
sc.close();
}
}