题目描述
新年快到了，笑笑打算给他的好朋友们发贺年卡，而且他已经选好了自己要购买的贺卡的样式。
俗话说得好，货比三家，笑笑来到商店，看了各个商铺这种贺卡的价钱。不仅如此，笑笑还记住了每个商铺的存货量。已知笑笑打算购买 mm 张贺卡，问他最少花多少钱。
输入
第一行两个整数 mm 和 nn 。其中 mm 表示要购买的贺卡的数量，nn 表示商铺的个数。
以下 nn 行，每行两个整数，分别表示该商铺这种贺卡的单价和存货量。
输出
仅一个数，表示笑笑花的最少钱数。
样例
输入
10 4 4 3 6 2 8 10 3 6
输出
36
数据规模
0<m,n≤10000<m,n≤1000，每个商铺贺卡单价在 1∼1001∼100 之间，数量在 1∼10001∼1000 之间，输入保证商铺的总存货量不少于 mm 。
这道题是非常经典的贪心算法入门题，核心思路就是「优先买单价最便宜的商铺的贺卡，把便宜的买光再买下一家稍贵的」
贪心（Greedy Algorithm）是编程里一种非常直观的算法思想，核心可以用一句话概括：在每一步决策的时候，都选择当前局部看来最优的选项，期望通过每一步的局部最优，最终得到全局的最优解。
#include<iostream> #include<vector> #include<algorithm> //STL sort头文件必须引入 using namespace std; //自定义结构体，存储每个商铺的单价和存货量 struct Shop{ int price; int stock; }; int main(){ int m, n; cin >> m >> n; vector<Shop> shops(n); //用STL的vector存储所有的商铺数据 for(int i = 0; i < n; i++){ cin >> shops[i].price >> shops[i].stock; } sort(shops.begin(),shops.end(),[](const Shop& a,const Shop& b){ return a.price < b.price; }) ; int total_cost = 0; //记录总花费 int remaining = m; //还需购买 for(int i = 0; i < n; i++){ int buy_num = min(remaining, shops[i].stock); total_cost += buy_num * shops[i].price; remaining -= buy_num; if(remaining == 0) break; } cout << total_cost << endl; return 0; }sort(shops.begin(), shops.end(), 自定义比较函数)是STL sort的标准用法：前两个参数是排序的起止迭代器，第三个参数是你自己定义的排序规则，这里用C++11的lambda表达式写非常简洁，作用就是告诉sort“按price小的排在前面”。// 函数返回值是bool，也就是只能返回true或者false // 两个参数a和b，就是sort每次拿来比较的两个商铺对象，加const &是为了不拷贝、不修改数据，你现在可以先理解成固定写法 bool 我判断两个商铺谁在前(Shop a, Shop b) { // 我明明白白告诉sort：如果a的单价 < b的单价 → 就返回true，代表a应该排在b左边（前面） return a.price < b.price; }- 你也可以不用lambda，单独写一个比较函数效果完全一样：
bool compare(const Shop& a, const Shop& b) { return a.price < b.price; } // sort调用时写 sort(shops.begin(), shops.end(), compare);具体代码如下：
#include <iostream> #include <algorithm> using namespace std; // 先定义商铺的结构体 struct Shop { int price; // 单价 int stock; // 存货 }; // 就写这个最朴素的比较函数，没有任何新语法 bool cmp(Shop a, Shop b) { // 规则：单价小的，排在前面 return a.price < b.price; } int main() { int m, n; cin >> m >> n; Shop shops[1005]; for(int i=0; i<n; i++) { cin >> shops[i].price >> shops[i].stock; } // 把cmp传给sort，sort就会按单价从小到大排好所有商铺 sort(shops, shops + n, cmp); // 接下来直接贪心买就完事 int totalCost = 0; for(int i=0; i<n; i++) { if(m <= 0) break; // 当前店的货够买剩下的所有，直接买完结束 if(shops[i].stock >= m) { totalCost += m * shops[i].price; m = 0; } else { // 把这家店的货全买空 totalCost += shops[i].stock * shops[i].price; m -= shops[i].stock; } } cout << totalCost << endl; return 0; }
