Codeforces Educational Round2 B

問題

codeforces.com
配列aと配列bの長さnとmが与えられ、整数型の配列aとbが与えられる。
0 <= i < mにおいて、配列aの中にb[i]以下の要素がいくつあるかを出力する。

解法

配列aをソートして、各b[i]ごとに配列aに対して二分探索を行って、b[i]と同じ値がある場合は
b[i]と同じ値の中で一番要素番号が大きいもの + 1、無い場合はb[i]より大きい値の中で一番要素番号が小さいものを + 1
したものをb[i]以下の要素の個数として出力する。

注意

(ここに関してはあくまで私の推測なので誤っていたら教えてくれると勉強になります。)
下記のソースコードで配列aをソートする前にrandomSort()でランダムに並び替えているのは
JavaのArrays.sort()を使う関係でArrays.sort()ではクイックソートを使うっぽくて
クイックソートの性質上、最悪計算量がO(n^2)になる場合があるからです。
実際にrandomSort()を抜かして実行したらあるテストケースで落ちました。

ソースコード

import java.util.Arrays;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class B
{
    public void randomSort(int[] t)
    {
        for(int i = 0;i < t.length;i++)
        {
            int random = (int)(Math.random() * t.length);
            int tmp = t[i];
            t[i] = t[random];
            t[random] = tmp;
        }
    }
    public void solve()
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = null;
        try
        {
            line = br.readLine().split(" ");
        }catch(IOException e)
        {
            e.printStackTrace();
        }
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int[] a = new int[n];
        try
        {
            line = br.readLine().split(" ");
        }catch(IOException e)
        {
            e.printStackTrace();
        }
        for(int i = 0;i < n;i++)
        {
            a[i] = Integer.parseInt(line[i]);
        }
        randomSort(a);
        Arrays.sort(a);
        try
        {
            line = br.readLine().split(" ");
        }catch(IOException e)
        {
            e.printStackTrace();
        }
        for(int i = 0;i < m;i++)
        {
            int b = Integer.parseInt(line[i]);
            int left = 0;
            int right = a.length - 1;
            int mid;
            while(left < right)
            {
                mid = (left + right) >>> 1;
                if(a[mid] <= b)
                {
                    left = mid + 1;
                }else
                {
                    right = mid - 1;
                }
            }
            if(a[left] <= b)left++;
            if(i != 0)System.out.print(" ");
            System.out.print(left);
        }
        System.out.println();
    }
    public static void main(String[] args)
    {
        new B().solve();
    }
}