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