C++编程解决:新年快到了,笑笑打算给他的好朋友们发贺年卡,而且他已经选好了自己要购买的贺卡的样式。俗话说得好,货比三家,笑笑来到商店,看了各个商铺这种贺卡的价钱。不仅如此,笑笑还记住了每个商铺的存货量。已知笑笑打算购买m张贺卡,问他最少花多少钱。
时间: 2024-03-22 09:41:59 浏览: 112
这道题可以使用贪心算法来解决。我们可以将每张贺卡的价格和存货量存储在一个二元组中,然后按照价格从小到大排序。接着,我们可以从价格最低的贺卡开始购买,每次购买一张贺卡,直到购买满m张贺卡或者某个商铺的存货量不足。
C++代码如下:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> cards(n); // 存储每张贺卡的价格和存货量
for (int i = 0; i < n; i++) {
cin >> cards[i].first >> cards[i].second;
}
sort(cards.begin(), cards.end()); // 按价格从小到大排序
int ans = 0;
int cnt = 0; // 已购买的贺卡数量
for (int i = 0; i < n && cnt < m; i++) {
int num = min(m - cnt, cards[i].second); // 还需要购买的数量
ans += num * cards[i].first;
cnt += num;
}
cout << ans << endl;
return 0;
}
```
输入样例:
```
5 8
3 2
5 3
2 1
8 4
6 5
```
输出样例:
```
51
```
解释:购买3张价值为2的贺卡,2张价值为3的贺卡,3张价值为5的贺卡,共计51元。
阅读全文