The Lonely Girl's Lie(AOJ No.0272)

N
a1 a2 ... aN
b1 b2 ... bN
が与えられる。
aiはAがもっているパケモンのレベルbiはBがもっているパケモンのレベルを示す。
パケモンを戦わせたとき、レベルが高い方が勝つ。同レベルなら引き分け。
お互いk匹パケモンを選んで１対１でk回戦したとき、Aの勝ち数が必ずk/2より大きくなるようなkの最小値を求める。
どう選んでも勝てない場合はNAと答える。
制約
1 ≤ N ≤ 40000
1 ≤ ai,bi ≤ 100000
1 ≤ k < N

アルゴリズム

お互いの最前手は強い順でk匹選んだ場合。
強い順にソートし、
kを増やしながら2分探索して
Aの勝ち数 = k - Bの勝ちor引き分け数
を求める。
境界条件を間違えないようにする。
k == NはNA

コード

Collections.reverseOrder()便利。プリミティブ型には使えないけど。
Memory Limit Exceededたくさん出した。
毎回配列を生成したり、コンパレータを渡しているのがまずいのかと思って直して提出してみたけど、
やっぱりMemory Limit Exceededじゃないか...（呆れ）
System.gc()を入れてとおりました。競技プログラミングでガーベジコレクションとか正気か？

import java.util.*;
public class aoj0272 {
    static final Scanner stdin = new Scanner(System.in);
    public static void main(String[] args) {
        while (true) {
            int n = stdin.nextInt();
            if (n == 0) break;
            System.gc();
            Integer[] a = new Integer[n], b = new Integer[n];
            for (int i = 0; i < n; ++i) a[i] = stdin.nextInt();
            for (int i = 0; i < n; ++i) b[i] = stdin.nextInt();
            Arrays.sort(a, Collections.reverseOrder());
            Arrays.sort(b, Collections.reverseOrder());
            int k = n;
            for (int i = 0, bNotFail = 0; i < n; ++i) {
                k = i+1;
                int pos = lowerBound(b, a[i]-1, Collections.reverseOrder())-1;
                if (bNotFail <= pos) ++bNotFail;
                if ((k - bNotFail) > k/2) break;
            }
            System.out.println(k < n ? k : "NA");
        }
    }
    public static <T> int lowerBound(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c){
        int lb = fromIndex - 1, ub = toIndex;
        while(ub - lb > 1){          //rage of solution > 1
            int mid = (lb + ub) / 2, cmp = c.compare(a[mid], key);
            if( cmp >= 0 )   ub = mid;   //(lb,mid]
            else            lb = mid;   //(mid,ub]
        }
        return ub;                      //(lb, ub], ub = lb + 1 → [ub, ub+1)
    }
    public static <T> int lowerBound(T[] a, T key, Comparator<? super T> c){
		return lowerBound(a, 0, a.length, key, c);
	}
}