[Java] UVa 501 Black Box

題目連結

題意:
大致上描述一個資料庫，有 GET 跟 ADD(x) 兩種指令。ADD(x) 會新增一個元素 x 到 BOX，GET指令則會讓 (i + 1)，並輸出當前 BOX 中第 i 小的數。

問題可以簡化為依序執行 ADD(x) 指令(題目測資A(1), A(2), ..., A(M))，當 BOX 內元素個數達到GET指令的值時，則先執行 GET 指令( GET 指令序列是嚴格遞增的)(u(1), u(2), ..., u(N))

解法:
是依序讀入 GET 指令的值，並用一個變數紀錄當前的 BOX 內元素個數。如果元素個數不足，就開始讀 ADD(x) 指令補充。由於BOX內元素都是由小到大排列的，在每次將數字加進來的同時，透過二分搜尋法尋找該元素要插入的位置(一開始我是從 BOX 頭開始判斷，結果超時( TLE )了)，最後依序讀取GET指令的index輸出 BOX 內第 i 個小的數輸出。

import java.util.*;
public class main{
    public static void main(String[] args) {
        try{
            int K, M, N;
            int A[] = new int[30100];
            int u[] = new int[30100];
            int Box[] = new int[30100];
            Scanner in=new Scanner(System.in);
            

            K = in.nextInt();
            
            while(K-- > 0){
             M = in.nextInt();
             N = in.nextInt();
             for(int i = 1 ;i <= M; i++) {
              
              A[i] = in.nextInt();
             }
             for(int i = 1 ;i <= N; i++) {
              u[i] = in.nextInt();
             }
             
            
             int size = 0, index = 0;
          for(int i = 1; i <= N; i++)
          {
              while(size < u[i])
              {
                  size ++;
                  int key = A[size];
                  

                  int l = 1, r = size - 1, m;
                  while(l <= r)
                  {
                      m = (l + r) / 2;
                      if(Box[m] < key)
                          l = m + 1;
                      else
                          r = m - 1;
                  }
 
                  for(int j = size - 1; j >= l; j--)
                      Box[j + 1] = Box[j];
                  Box[l] = key;
              }
 
              index++;
              System.out.println(Box[index]);
          }
             if(K > 0)
             System.out.println();
            }
            
        }catch(Exception e){
            System.out.println("Input error!");
        }
    }
}