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行)

ARC094の他の問題 C D F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告