[アルゴリズムの問題を解く]白俊19637 IFの文章を書いてください.

今日は白駿19637-IFドアを書いてくれが解けました.
質問する
ゲーム開発者のミリーは戦闘力システムを作り、キャラクターが持つ戦闘力を基準に称号を貼り付けた.
例えば、戦力10000以下のキャラにはWEAK、10000および100000以下のキャラにNORMAL、100000および100000以下のキャラにSTRONG称号を付ける.これをIF文と書くと、次のようになります.

if power <= 10000
 print WEAK
else if power <= 100000
 print NORMAL
else if power <= 1000000
 print STRONG

独自のゲーム開発に忙しいミリーの代わりに、キャラクターの戦闘力に合った称号を作成するプログラム.
入力
1行目では、称号の個数N(1≦N≦10^5)と、称号を出力するキャラクタの個数M(1≦M≦10^5)との間にスペースがある.(1 ≤ N, M ≤ 10^5)
2行目から始まるN行には、各称号の名称、長さが1より大きく、長さが11より小さい英語の大文字、およびその称号の戦闘力上限値が109より小さい負の値を表す整数が与えられる.称号は戦闘力上限値の降雨順で与えられる.
N+2行から、M行ごとに与えられるのはキャラクターの戦闘力を表す音ではなく整数です.該当する称号がない戦闘力は入力として与えられない.
しゅつりょく
Mライン上では、キャラクターの戦闘力に合った称号を入力順に出力します.あるキャラクターに戦闘力で出力できる称号が複数ある場合、最初に入力した称号のみが出力されます.
例
入力します.

3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000

出力します.

WEAK
WEAK
WEAK
NORMAL
NORMAL
NORMAL
STRONG
STRONG

入力します.

3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000

出力します.

B
B
C
C
C

解答方法
実はこの探索分類が問題を解き始めたのを見た.しかし,NとMの入力範囲が(1≦N,M≦10^5)であれば,ある程度探索によって解決すればタイムアウトが生じる.そうなると有効な探索方法が悩み、この問題は各範囲に含まれる範囲を探すことであり、各範囲は順番に与えられるので、二分探索に適した問題を見つけることができる.
上記のように、私が探しているのは、与えられた値が属する範囲です.したがって,各範囲の基準値を配列に入れ,配列のインデックスで二分検索を行う.最小の範囲を他の範囲と一致させるために、戦闘力となる範囲の最小値が0未満の値を基準として並べ替えられる最初の要素を一緒に置く.

power <= 가장 작은 기준값

同じ基準値を入力できる条件があります.これを入力でフィルタリングしていないので、同じ範囲があれば一番前の範囲を見つけなければならないので、以下のように左、右リフレッシュ基準を設定しました.

if(threshold[mid] >= power) right = mid;

また、求めるのは範囲であるため、左と右の差が1であれば、求めるのは範囲であることを示すため、ナビゲーションを終了し、出力する値が範囲の上限標準値であるため、右側に戻った.この場合、範囲基準値は同じである可能性があるので、前述したように一番前の範囲を検索することが実現されたが、その範囲の下限基準値と上限基準値は同じである可能性があるので、この場合、一番前の名前を返すために、条件にleftを返す.
この探索問題は面白いと思います.今度の问题もおもしろくて、どうして私に说明させないのですか.私は説明が好きではありません.私は後で読んでも理解できません.説明が理解できなければコードを見ればいいです!
コード#コード#

import java.io.*;
import java.util.*;

public class Main {

    static class Solution{
        private int[] thresholds;
        private int left, right, mid;
        Solution(int[] thresholds){
            this.thresholds = thresholds;
        }

        int solution(int power){
            left = 0;
            right = thresholds.length-1;
            mid = right;
            while(right-left > 1){
                mid = (right+left)/2;
                if(thresholds[mid] >= power) right = mid;
                else left = mid;
            }
            if(thresholds[left] == thresholds[right]) return left;
            return right;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
        StringTokenizer st; // tokenizer

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String[] names = new String[n+1];
        int[] thresholds = new int[n+1];
        thresholds[0] = -1;
        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            names[i] = st.nextToken();
            thresholds[i] = Integer.parseInt(st.nextToken());
        }
        Solution solution = new Solution(thresholds);
        for(int i=0; i<m; i++){
            bw.write(names[solution.solution(Integer.parseInt(br.readLine()))] + "\n");
        }
        
        bw.flush(); // flush
        bw.close(); // close
        br.close(); // close
    }
}