本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Bargain Sale Selection【题目描述】Takahashi will purchase allN NNitems, one of each.高桥将购买全部N NN件商品每样一件。Each item has two prices: a “regular price” and a “sale price.” The regular price of itemi ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)isA i A_iAi​yen, and the sale price isB i B_iBi​yen. It is guaranteed that the sale price is at most the regular price, that is,B i ≤ A i B_i \leq A_iBi​≤Ai​.每件商品有两种价格“原价和促销价”。商品i ii1 ≤ i ≤ N 1 ≤ i ≤ N1≤i≤N的原价为A i A_iAi​日元促销价为B i B_iBi​日元。保证促销价不超过原价即B i ≤ A i B_i ≤ A_iBi​≤Ai​。Takahashi has one special discount coupon. With this coupon, he can chooseat mostK KKitems from theN NNitems and purchase the chosen items at their sale prices. The remaining items that are not chosen will be purchased at their regular prices. Note that the same item cannot be chosen more than once, and it is also allowed to choose no items (i.e., choose0 00items).高桥有一张特殊折扣券。使用此券他可以从N NN件商品中最多选择K KK件并以促销价购买选中的商品。未选中的剩余商品将按原价购买。注意同一件商品不能被选择超过一次并且也可以选择0 00件商品即选择0 00件。When Takahashi optimally chooses which items to purchase at the sale price, find the minimum possible total cost of purchasing allN NNitems.当高桥以最优方式选择哪些商品以促销价购买时求购买全部N NN件商品的最小可能总费用。【输入】N NNK KKA 1 A_1A1​B 1 B_1B1​A 2 A_2A2​B 2 B_2B2​⋮ \vdots⋮A N A_NAN​B N B_NBN​The first line contains an integerN NNrepresenting the number of items and an integerK KKrepresenting the maximum number of items that can be purchased at the sale price, separated by a space.The followingN NNlines each contain, for thei ii-th line( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N), the regular priceA i A_iAi​and the sale priceB i B_iBi​of itemi ii, separated by a space.【输出】Print the minimum possible total cost of purchasing allN NNitems as an integer on a single line. Note that the answer may not fit within a32 3232-bit integer.【输入样例】3 2 100 80 200 150 300 250【输出样例】500【解题思路】【算法标签】#贪心#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005;intn,k,ans;// n: 物品数量k: 打折商品数量ans: 总花费structNode{intA,B;// A: 正常价格B: 打折后价格}a[N];// 比较函数按照 (A-B) 的差值从大到小排序// 即优先选择打折节省更多的商品boolcmp(Node x,Node y){returnx.A-x.By.A-y.B;}signedmain(){cinnk;// 读入商品总数和打折商品数量for(inti1;in;i){cina[i].Aa[i].B;// 读入正常价格和打折后价格}// 按照差价从大到小排序sort(a1,an1,cmp);// 前k个商品选择打折价for(inti1;ik;i){ansa[i].B;}// 剩余商品选择原价for(intik1;in;i){ansa[i].A;}coutansendl;// 输出最小总花费return0;}【运行结果】3 2 100 80 200 150 300 250 500