STL--贪心算法

题目描述新年快到了笑笑打算给他的好朋友们发贺年卡而且他已经选好了自己要购买的贺卡的样式。俗话说得好货比三家笑笑来到商店看了各个商铺这种贺卡的价钱。不仅如此笑笑还记住了每个商铺的存货量。已知笑笑打算购买 mm 张贺卡问他最少花多少钱。输入第一行两个整数 mm 和 nn 。其中 mm 表示要购买的贺卡的数量nn 表示商铺的个数。以下 nn 行每行两个整数分别表示该商铺这种贺卡的单价和存货量。输出仅一个数表示笑笑花的最少钱数。样例输入10 4 4 3 6 2 8 10 3 6输出36数据规模0m,n≤10000m,n≤1000每个商铺贺卡单价在 1∼1001∼100 之间数量在 1∼10001∼1000 之间输入保证商铺的总存货量不少于 mm 。这道题是非常经典的贪心算法入门题核心思路就是「优先买单价最便宜的商铺的贺卡把便宜的买光再买下一家稍贵的」贪心Greedy Algorithm是编程里一种非常直观的算法思想核心可以用一句话概括在每一步决策的时候都选择当前局部看来最优的选项期望通过每一步的局部最优最终得到全局的最优解。#includeiostream #includevector #includealgorithm //STL sort头文件必须引入 using namespace std; //自定义结构体存储每个商铺的单价和存货量 struct Shop{ int price; int stock; }; int main(){ int m, n; cin m n; vectorShop 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的标准用法前两个参数是排序的起止迭代器第三个参数是你自己定义的排序规则这里用C11的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 i0; in; i) { cin shops[i].price shops[i].stock; } // 把cmp传给sortsort就会按单价从小到大排好所有商铺 sort(shops, shops n, cmp); // 接下来直接贪心买就完事 int totalCost 0; for(int i0; in; 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; }