『こちらを探索』BOJ 14434アトラクション1
質問する
問題の背景から見ると、すべての児童の初日の身長は0で、各児童の身長は1で、この日の長さはkの順に並んでいます.この場合、i児とj児が身長制限のあるkアトラクションに乗れるという質問は全部でq個あり、所定の時間内に日付ごとに何個回答できるかという質問があります.
に近づく
すべての問題について、日付を基準に二分探索を行い、最初にアトラクションに乗れる日を探します.(身長が下がらないので初日から最終日まで搭乗可能)
特定の日に2人の子供が対応するアトラクションに乗れるかどうかを判断しなければならない.
->時間的複雑度はO(q87 logk87 k)O(q*logk*k)O(q87 logk87 k)であり,問題制限の解法に合致しない.
->最終的にはソートが必要なため、2-1よりも時間的に複雑です.
時間複雑度O(q87 logk87 logk)O(q*logk*logk)O(q87 logk87 logk)が利用可能です.
予め長さkの解答配列(初期化0)を設定しておき、各質問に搭乗可能な初日が得られ、その後[搭乗可能な初日]+1と回答する.
すべての質問の検索が終了すると、残りの答えをインデックス1から最後の順に検索し、答え[i]に答え[i-1]を追加します.i-1から搭乗可能な質問に答えてi-1から最後まで答えられるからです.
解答案を出力すると正解が得られます
コード#コード#
import java.io.*;
import java.util.*;
class Main {
static int n;
static int m;
static int k;
static int q;
static int[] limit;
static ArrayList<Integer>[] list;
static int find(int day, int child1) {
int l = -1;
int r = list[child1].size();
while (l + 1 < r) {
int mid = (l + r) / 2;
if (list[child1].get(mid) <= day) {
l = mid;
} else {
r = mid;
}
}
return l + 1;
}
static boolean check(int day, int child1, int child2, int ride) {
int height1 = find(day, child1);
int height2 = find(day, child2);
if (height1 + height2 >= limit[ride - 1]) {
return true;
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
n = Integer.parseInt(temp[0]);
m = Integer.parseInt(temp[1]);
k = Integer.parseInt(temp[2]);
q = Integer.parseInt(temp[3]);
temp = br.readLine().split(" ");
limit = new int[m];
for (int i = 0; i < m; i++) {
limit[i] = Integer.parseInt(temp[i]);
}
list = new ArrayList[n + 1];
for (int i = 0; i < n + 1; i++) {
list[i] = new ArrayList<>();
}
temp = br.readLine().split(" ");
for (int i = 0; i < k; i++) {
list[Integer.parseInt(temp[i])].add(i);
}
int[] answer = new int[k];
for (int i = 0; i < q; i++) {
temp = br.readLine().split(" ");
int u = Integer.parseInt(temp[0]);
int v = Integer.parseInt(temp[1]);
int ride = Integer.parseInt(temp[2]);
int l = -1;
int r = k;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid, u, v, ride)) {
r = mid;
} else {
l = mid;
}
}
if (r == k)
continue;
answer[r] += 1;
}
for (int i = 1; i < k; i++) {
answer[i] += answer[i - 1];
}
for (int i = 0; i < k; i++) {
System.out.println(answer[i]);
}
}
}
Reference
この問題について(『こちらを探索』BOJ 14434アトラクション1), 我々は、より多くの情報をここで見つけました https://velog.io/@since-1994/이분-탐색-BOJ-14434-놀이기구-1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol