No.1282 Display Elements
タグ : / 解いたユーザー数 172
作問者 :
platinum
/ テスター :
leafirby
問題文
A君、B君はそれぞれ$\ N\ $枚のカードを持っています。
$i\ $番目のカードには、それぞれ正の整数$\ a_i,\ b_i\ $が書かれています。
二人はこれから次の操作を繰り返します。$i\ $回目 $(i=1,\ 2,\ \dots,\ N)$ の操作は次の通りです。
・B君が$\ i\ $番目のカードを場に出す。次にA君がまだ選んでいないカードから一枚選んで提示する。
・A君が提示したカードに書かれた整数と、場にあるカードに書かれた整数を一枚ずつ比較する。
提示したカードに書かれた整数の方が大きいたびに、A君は$\ 1\ $点を得る。
このとき、A君が獲得できる得点の最大値を求めてください。
22:16 追記：「カードの数字」という表現を、「カードに書かれた整数」に変更しました。
入力
$N$ $a_1\ a_2\ \dots\ a_N$ $b_1\ b_2\ \dots\ b_N$
・入力は全て整数である。
・$1 \le N \le 10^5$
・$1 \le a_i, b_i \le 10^9$
出力
A君が獲得できる得点の最大値を出力してください。
サンプル
サンプル1
入力
2 1 5 3 4
出力
2
はじめにB君が $3$ が書かれた一枚目のカードを場に出します。
A君は $1$ を提示するべきですが $1$ ターン目は得点を獲得できません。
次にB君が $4$ が書かれた二枚目のカードを場に出します。
A君は残った $5$ が書かれたカードを提示します。これは $3$, $4$ より大きく、 $2$ 点を獲得します。
提示する順番を逆にすると $1$ 点しか獲得できないので、得点の最大値である $2$ を出力します。
サンプル2
入力
3 2 2 2 1 5 3
出力
3
このケースではどのような順番でカードを提示しても結果は変わりません。
サンプル3
入力
7 3 10 7 2 5 7 1 8 5 21 9 1 6 4
出力
11
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。