ARC094 E : Tozan and Gezan(700)
作成日：2018.09.04
最終更新日：2018.09.04
問題概要
非負整数からなり、要素の総和が等しい2つの数列$\{A_i\}$,$\{B_i\}$が等しくなるまで操作「Aliceが$A_i$のうち正の要素を1つ選び$1$減らした後、Bobが$B_i$のうち正の要素を1つ選び$1$減らす」を繰り返す。
Aliceは操作の回数を最大に、Bobは操作の回数を最小にするために最適な行動をとった時、操作が行われる回数を求めよ。
制約
$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i , B_i \leq 10^9$
$\sum A_i = \sum B_i$
考え方
$A_i \gt B_i$となっている要素をAliceが選ばなければ、2つの数列は等しくならない。
この要素を選ばざるを得なくなるのは、他の要素がすべて$0$になった時である。
このことから、$A_i \gt B_i$を満たす要素のうち$B_i$が最小となるものを最後まで選ばないのがAliceの最適戦略である。
Bobは$A_i \lt B_i$となっている要素を選び続けるのが最適である。
2つの数列の総和が等しいことから、このような要素がない時は2つの数列は等しくなっていることが分かる。
以上より答えは$\sum A_i$$-min_{\{i|A_i \gt B_i\}}B_i$であることが分かる。
但し、初めから2つの数列が等しければ$0$が答えであることに注意する。
ソースコード
マクロ等はこちら
const LL INF = 1e9 + 7;
int main(){
int N; cin >> N;
LL s = 0 , m = INF;
repp(i,0,N){
LL A,B; cin >> A >> B;
s += A;
if(A > B) m = min(m,B);
}
cout << (m==INF?0:s-m) << endl;
return 0;
}解法まとめ
2つの数列が等しければ$0$、そうでなければ$\sum A_i$$-min_{\{i|A_i \gt B_i\}}B_i$が答えである。(5-11行)