![题解：洛谷 P14635 [NOIP2025] 糖果店](http://pic.xiahunao.cn/yaotu/题解：洛谷 P14635 [NOIP2025] 糖果店)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14635 [NOIP2025] 糖果店 - 洛谷【题目描述】小 X 开了一家糖果店售卖n nn种糖果每种糖果均有无限颗。对于不同种类的糖果小 X 采用了不同的促销策略。具体地对于第i ii(1 ≤ i ≤ n 1 \le i \le n1≤i≤n) 种糖果购买第一颗的价格为x i x_ixi元第二颗为y i y_iyi元第三颗又变回x i x_ixi元第四颗则为y i y_iyi元以此类推。小 R 带了m mm元钱买糖果。小 R 不关心糖果的种类只想得到数量尽可能多的糖果。你需要帮助小 R 求出m mm元钱能购买的糖果数量的最大值。【输入】输入的第一行包含两个正整数n , m n, mn,m代表糖果的种类数和小 R 的钱数。输入的第i 1 i1i1(1 ≤ i ≤ n 1 \le i \le n1≤i≤n) 行包含两个正整数x i , y i x_i, y_ixi,yi分别表示购买第i ii种糖果时第奇数颗的价格和第偶数颗的价格。【输出】输出一行一个非负整数表示m mm元钱能购买的糖果数量的最大值。【输入样例】2 10 4 1 3 3【输出样例】4【算法标签】#普及 #反悔贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,m,ans;// n: 物品数量m: 总预算ans: 最大价值structNode{intx,y;// x: 购买价格y: 回收价格}a[N];boolcmp(Node x,Node y)// 排序比较函数按购买价格升序排序{returnx.xy.x;}signedmain(){cinnm;// 输入物品数量和总预算intminS1e18;// 初始化最小成本为无穷大for(inti1;in;i)// 输入每个物品的信息{intx,y;cina[i].xa[i].y;// 输入购买价格和回收价格minSmin(minS,a[i].xa[i].y);// 更新最小成本购买回收的价格}sort(a1,an1,cmp);// 按购买价格升序排序intsum0;// 已花费的总和for(inti0;in;i)// 遍历前i个物品i从0到n{suma[i].x;// 累计购买价格if(msum)// 如果总预算不够购买前i个物品continue;// 跳过当前i// 计算当前方案的最大价值// 先购买前i个物品剩余的钱可以多次购买回收最便宜的商品// (m - sum)/minS * 2: 剩余预算可购买的次数 * 2买入卖出一次算2次操作// i: 已经购买的物品数量ansmax(ans,(m-sum)/minS*2i);}coutansendl;// 输出最大价值return0;}【运行结果】2 10 4 1 3 3 4
题解：洛谷 P14635 [NOIP2025] 糖果店
发布时间：2026/5/20 22:23:35
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14635 [NOIP2025] 糖果店 - 洛谷【题目描述】小 X 开了一家糖果店售卖n nn种糖果每种糖果均有无限颗。对于不同种类的糖果小 X 采用了不同的促销策略。具体地对于第i ii(1 ≤ i ≤ n 1 \le i \le n1≤i≤n) 种糖果购买第一颗的价格为x i x_ixi元第二颗为y i y_iyi元第三颗又变回x i x_ixi元第四颗则为y i y_iyi元以此类推。小 R 带了m mm元钱买糖果。小 R 不关心糖果的种类只想得到数量尽可能多的糖果。你需要帮助小 R 求出m mm元钱能购买的糖果数量的最大值。【输入】输入的第一行包含两个正整数n , m n, mn,m代表糖果的种类数和小 R 的钱数。输入的第i 1 i1i1(1 ≤ i ≤ n 1 \le i \le n1≤i≤n) 行包含两个正整数x i , y i x_i, y_ixi,yi分别表示购买第i ii种糖果时第奇数颗的价格和第偶数颗的价格。【输出】输出一行一个非负整数表示m mm元钱能购买的糖果数量的最大值。【输入样例】2 10 4 1 3 3【输出样例】4【算法标签】#普及 #反悔贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,m,ans;// n: 物品数量m: 总预算ans: 最大价值structNode{intx,y;// x: 购买价格y: 回收价格}a[N];boolcmp(Node x,Node y)// 排序比较函数按购买价格升序排序{returnx.xy.x;}signedmain(){cinnm;// 输入物品数量和总预算intminS1e18;// 初始化最小成本为无穷大for(inti1;in;i)// 输入每个物品的信息{intx,y;cina[i].xa[i].y;// 输入购买价格和回收价格minSmin(minS,a[i].xa[i].y);// 更新最小成本购买回收的价格}sort(a1,an1,cmp);// 按购买价格升序排序intsum0;// 已花费的总和for(inti0;in;i)// 遍历前i个物品i从0到n{suma[i].x;// 累计购买价格if(msum)// 如果总预算不够购买前i个物品continue;// 跳过当前i// 计算当前方案的最大价值// 先购买前i个物品剩余的钱可以多次购买回收最便宜的商品// (m - sum)/minS * 2: 剩余预算可购买的次数 * 2买入卖出一次算2次操作// i: 已经购买的物品数量ansmax(ans,(m-sum)/minS*2i);}coutansendl;// 输出最大价值return0;}【运行结果】2 10 4 1 3 3 4
