問題

問題文

高橋君はキャベツ屋さんにやってきました。
キャベツ屋さんでは、 キャベツを 1 個 X 円で買うことができます。
ただし、キャベツを A 個よりも多く買う場合、A+1 個目以降に買うキャベツについては 1 個 Y 円で買うことができます。（ここで、Y < X が保証されます。）
高橋君がキャベツを N 個買うために必要な金額を出力してください。

制約

1 ≤ N ≤ 10^5
1 ≤ A ≤ 10^5
1 ≤ Y < X ≤ 100
入力はすべて整数

考察

まとめ買いすると安くなる商品を買っていきます。for文を回してもいいのですが、ABCのA問題は繰り返し処理を使わなくても解ける問題が出題されているらしいので、計算で解いてみます。

まず、A個まではX円で購入可能ですので、

A*X

としたいのですが、もし「A個も商品を買わないよ」っていう場合には困ってしまいます。ですので、NとAの小さい方の値を採用しましょう。

X * min(N, A)

次にA+1以降です。これ以降は1個当たりY円で購入可能です。また、Y円の対象となるのは総数NからAを引いた個数です。ですので、

Y*(N-A)

としたいのですが、先ほどと同様にダメなケースがあります。NがAよりも小さい場合です。この場合にはN-Aが負になりますので、買えば買うほど合計金額が減っていきます。ですので、Y円で購入するのは最小でも0個としておきましょう。

Y * max( N-A,0)

以上を組み合わせた。

X * min(N, A) + Y * max( N-A,0)

が答えになります。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

int main()
{
	int n, a, x, y;
	cin >> n >> a >> x >> y;
	int ans = min(n, a) * x + max(0, n - a) * y;
	cout << ans << endl;
	return 0;
}

あとがき

今回は計算で求めましたが、for文にて1個ずつ購入しても求めることが可能です。私もコンテスト中は計算の場合分けで混乱したので、何も考えずにfor文を書きました。コンテスト中はどんな方法でも早く正確に解くのが正義ですので柔軟に対応しましょう。そしてコンテスト後にしっかりと復習をしておきましょう。