Cまで三完。
No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
一応自力AC。
二分探索し、P番目の価格の値が求まれば、復元は難しくなさそう。が、コンテスト中は二分探索の判定方法で詰まり解けなかった。
ソートして二分探索して……では、同じ色の場合の処理が難しい。
こういうときは、片側だけ色で分類すると良い。半分全列挙のときと同じ感じでやれる。
各トップスに対して、
・全体で何個が価格X以下か？
・同じ色のものについて、何個が割引せずに価格X以下で、割引した後価格X以下か？
はどちらも二分探索で求められるので、判定できる。
復元は簡単だと思ったが、復元でも詰まった。
同じ色のものが答えになるときは簡単。
そうでないときは、価格Xになるものの個数がbisect(A,X)-bisect(A,X-1)で求まることを利用した。
全体で、価格Xになる個数と、同じ色で価格Xになる個数を比較し、全体の方が多くなっていればOK。
0 件のコメント:
コメントを投稿