Codeforces 387(#227 Div2 only) B. George and Round
問題
n問のコンテストを作る。i番目の問題の難易度はa[i]になるようにしたい。
持ってる問題はm問あって、i番目の難易度はb[i].
問題の難易度はコスト0で小さくすることができるが、大きくすることはできない。
コンテストを開催するためには何問新たに問題を作らなければならないか、最小値を求めよ。
制約条件
n, m≦3000
a[i], b[i]≦10^6で、どちらも小さい順に並んでいる
a[i]は全て相異なる
方針
難しい問題から準備していく。
a[i]にできる問題があればそれを使えばいいし、ないなら作る。
難しい順にa[i]を見ていけば、a[i]にするb[i]はどれでもいい。
(今のa[i]にするためのb[i]より、もっとギリギリのb[j]で作ったところで、
どうせ次のa[i-1]以降ではb[j]からでも当てはめられるから節約する意味がない)
int n, m, a[3000], b[3000]; int main(){ cin >> n >> m; rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; int ans = 0; for(int i = n - 1, j = m - 1; i >= 0; i--){ if(j >= 0 && a[i] <= b[j]) j--; else ans++; } cout << ans << endl; return 0; }