题目描述
某商店目前库存可乐数量为 k 瓶。
可乐的进货价格如下:
整箱:c 元/箱。每箱有 n 瓶。
单瓶:d 元/瓶。
请问,为了使得库存可乐数量不低于 n×m 瓶,该商店至少需要花费多少元钱来购进可乐。
显然,当 k≥n×m 时,无需购进可乐。
输入格式
第一行包含两个整数 c,d。
第二行包含两个整数 n,m。
第三行包含整数 k。
输出格式
一个整数,表示最少花费的金额。
数据范围
前 4 个测试点满足 1≤c,d,n,m,k≤10。
所有测试点满足 1≤c,d,n,m,k≤100。
样例
输入样例1:
1 10
7 2
1
输出样例1:
2
输入样例2:
2 2
2 1
2
输出样例2:
0
算法1
O(1)
简单数学题
有三种买卖情况:
1.
全买单瓶
2.
全买整箱
3.
既有单瓶,也有整箱
结果取最小即可
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int c, d, n, m, k;
scanf("%d%d%d%d%d", &c, &d, &n, &m, &k);
if (n * m <= k) puts("0");
else
{
long long res = n * m - k;
long long a = res / n * c + res % n * d;
long long b = res / n * c + c;
long long c = res * d;
printf("%lld\n", min(c, min(a, b)));
}
}
int main()
{
int t = 1;
while (t -- ) solve();
return 0;
}
算法2
(暴力枚举) $O(1)$
另外的思路便是比较单瓶的价格,这里分为整箱和单瓶,以及取余后的一箱价格与单瓶比较
思路是贪心,不过本质上和解法一一样
时间复杂度 O(1)
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int c, d, n, m, k;
scanf("%d%d%d%d%d", &c, &d, &n, &m, &k);
if (n * m <= k) puts("0");
else
{
long long res = n * m - k;
double a = c / n;
if (a < d)
{
if (c > res % n * d) printf("%lld\n", res / n * c + res % n * d);
else printf("%lld\n", res / n * c + c);
}
else printf("%lld\n", res * d);
}
}
int main()
{
int t = 1;
while (t -- ) solve();
return 0;
}