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; }

相关新闻

附近服务找不到?本地门店如何优化AI搜索推荐?

附近服务找不到?本地门店如何优化AI搜索推荐?

很多经营本地生活服务的商家最近发现一个现象:当用户直接向AI询问“附近哪家咖啡店好”或者“周边哪个家政靠谱”时,自家的门店却总是出现在推荐列表之外。即使门店在传统搜索引擎中排名尚可,但在生成式AI的问答中,似乎成了“隐形…

2026/11/18 2:53:45 阅读更多 →
中介数据频繁流失?房管家ACN私有化部署筑牢数据安全壁垒

中介数据频繁流失?房管家ACN私有化部署筑牢数据安全壁垒

对于房产中介而言,房源、客源、客户跟进记录就是门店的核心资产,更是门店生存发展的生命线。但行业普遍存在一个致命难题:员工离职带走客户、房源资源,核心数据随意外泄,门店多年积累的资产瞬间流失。很多门店做了多年…

2026/11/22 4:03:10 阅读更多 →
CANBridge-Ex 在煤矿防爆变频器中的应用

CANBridge-Ex 在煤矿防爆变频器中的应用

一、案例概述煤矿井下工作面普遍存在瓦斯、煤尘等爆炸性气体环境,对电气设备的防爆安全性提出了极为严苛的要求。防爆变频器作为煤矿综采、掘进、运输等核心设备的动力驱动单元,其通讯接口的本质安全设计直接关系到整套系统的安全运行。CANBridge-Ex 隔离…

2026/11/21 20:05:00 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/21 23:27:35 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/21 23:27:35 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/21 23:27:35 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/21 23:27:35 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/21 23:27:36 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/21 23:27:37 阅读更多 →

日新闻

周新闻

月新闻