ARC096 C : Half and Half(300)

作成日:2018.09.16
最終更新日:2018.09.16

問題概要

問題本文

 2種類のピザ$A,B$とそれらが半分ずつ組み合わさったピザ$AB$があり、それぞれの$1$枚当たりの価格は$A,B,C$である。 ピザ$A,B$をそれぞれ$X,Y$枚以上用意する時に必要な金額の最小値を求めよ。 但し、$2$枚のピザ$AB$を組み替えて、$1$枚ずつのピザ$A,B$にすることができる。
制約
$1 \leq A,B,C \leq 5000$
$1 \leq X,Y \leq 10^5$

考え方

 ピザ$A,B$をそれぞれ何枚買うかを決めれば、ピザ$AB$を何枚買うかが決まる。 しかしこれは$O(XY)$通りあるので間に合わない。
 逆にピザ$AB$を何枚買うかが決まれば、ピザ$A,B$をそれぞれ何枚買うかが決まる。 これは$O(max(X,Y))$通り試せば良いから全探索可能である。

ソースコード

マクロ等はこちら

int main(){
	int A,B,C,X,Y; cin >> A >> B >> C >> X >> Y;
	int ans = A * X + B * Y;
	repp(i,1,max(X,Y)+1) ans = min(ans , max(0,X-i)*A+max(0,Y-i)*B+2*i*C);
	cout << ans << endl;
	return 0;
}

解法まとめ

 ピザ$AB$を$2i$枚(奇数枚買っても無駄)買うと、ピザ$A,B$はそれぞれ$(X-i)$,$(Y-i)$枚以上買う必要がある。 $i$を$0$から$max(X,Y)$まで試して、最も必要な金額が少なかったものが答えである。(3-5行)

ARC096の他の問題 D E F

広告

自己紹介

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

プライバシーポリシー

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

お問い合わせ

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

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告