ABC474 E - One Time Coupon

考え方

このクーポンは、要は、$2$ つ同時に買うと片方は $B$ 円に値引きしてもらえるということ。
つまり、買い方として、以下の $3$ つを考えればよい。
購入済品を $2$ つ買うのはただの無駄なので考えなくてよい。

• 未購入品を $2$ つ選んで、片方を $A$ 円、片方を $B$ 円で買う
• 未購入品を $1$ つ、購入済品を $1$ つ選んで、片方を $A$ 円、片方を $B$ 円で買う
• 未購入品を $1$ つ選んで、$A$ 円で買う

ここで、$2$ 番目の買い方について考える。
割引の権利を利用して購入済品を再度買うのは損しかしない。
ということは、これを行うなら、未購入品を $B$ 円で、購入済品を $A$ 円で買うことになる。
ならば、購入済品としては $A$ が最小であるもののみ考えればよい。

つまり、これが役に立つのは、以下の $2$ つの条件を両方満たした場合である。

まず $1$ つめの条件として、未購入品の割引額が $A_{min}$ より大きいこと。
そうでなければ、$3$ 番目の買い方で未購入品を単品で買えばよい。

そして $2$ つめの条件として、未購入品 $2$ つ組の割引額がどちらも $2A_{min}$ より大きいこと。
そうでなければ、その未購入品 $2$ つをセットで買えばよい。

なるべく割引額が大きいものを $B$ で買うべきということも考えると、以下の貪欲法が成立する。

• 全ての商品の割引額を求め、昇順に並べておく
• 以下のどちらかになるまで、割引額最小の商品と最大の商品をセットにして $1$ 番目の方法で購入する
  • 残りの商品が $0$ 個または $1$ 個になる
  • 残りの商品の最小割引額が $2A_{min}$ より大きくなる
• 残りが $1$ 個だった場合、割引額が $A_{min}$ 以上なら $2$ 番目の方法で、そうでなければ $3$ 番目で買う
• 残りが $2$ 個以上だった場合、割引額が大きいものばかりなので、全て $2$ 番目の方法で買う

$2$ 番目の買い方をするときに $A_{min}$ であるものは必ず購入済になっている。
これは、割引額は $A$ より小さいことから成り立つ。

あらかじめ全て $B$ 円は払っておき、$A$ 円で払うものだけ追加支払いすると実装しやすい。
計算量はソート部分が支配的で $O(N\log N)$ となる。

入力例1での動作

入力を受け取る。

t: 3

n: 5
(a, b):
(11, 6)
(6, 5)
(2, 1)
(8, 3)
(7, 4)

n: 4
(a, b):
(5, 1)
(5, 2)
(5, 3)
(5, 4)

n: 6
(a, b):
(24, 13)
(24, 2)
(50, 12)
(35, 25)
(28, 26)
(10, 1)

まず、$1$ つ目のテストケースを考える。
$A_{min}=2$ であり、各商品の割引額 $A_i-B_i$ を昇順に並べると次のようになる。

1, 1, 3, 5, 5

あらかじめ全ての商品を $B$ 円で買うと考えると、最初に払う金額は $6+5+1+3+4=19$ 円である。

$2A_{min}=4$ なので、残りの割引額の最小値が $4$ 以下である間、最小と最大を組にする。

最後に割引額 $3$ の商品が $1$ つ残る。
$3>A_{min}(=2)$ なので、$A_{min}$ の商品を $A$ 円で再購入してクーポンを得て、この商品を $B$ 円で買う。
追加で $2$ 円払うことになり、答えは $23$ 円となる。

次に、$2$ つ目のテストケースを考える。
$A_{min}=5$、割引額を昇順に並べると次のようになる。

1, 2, 3, 4

全て $B$ 円で買う金額は $1+2+3+4=10$ 円である。
最小と最大を順に組にすると、$1$ 円、$2$ 円を追加で払うことになる。
したがって、答えは $10+1+2=13$ 円となる。

最後に、$3$ つ目のテストケースを考える。
$A_{min}=10$、割引額を昇順に並べると次のようになる。

2, 9, 10, 11, 22, 38

全て $B$ 円で買う金額は $13+2+12+25+26+1=79$ 円である。

$2A_{min}=20$ なので、最小と最大を順に組にする。

全ての商品を購入でき、答えは $100$ 円となる。

注意点

答えは int 型からはみ出る。
long long 型を用いること。

別解

特になし。