当前位置：首页 > news >正文

题解：AtCoder AT_awc0003_c Bargain Sale Selection

news 2026/4/24 22:39:12

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：C - 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_iAiyen, and the sale price isB i B_iBiyen. 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 ii（1 ≤ 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 KK
A 1 A_1A1B 1 B_1B1
A 2 A_2A2B 2 B_2B2
⋮ \vdots⋮
A N A_NANB 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_iAiand the sale priceB i B_iBiof 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

【输出样例】

【解题思路】

【算法标签】

#贪心#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn,k,ans;// n: 物品数量，k: 打折商品数量，ans: 总花费structNode{intA,B;// A: 正常价格，B: 打折后价格}a[N];// 比较函数：按照 (A-B) 的差值从大到小排序// 即优先选择打折节省更多的商品boolcmp(Node x,Node y){returnx.A-x.B>y.A-y.B;}signedmain(){cin>>n>>k;// 读入商品总数和打折商品数量for(inti=1;i<=n;i++){cin>>a[i].A>>a[i].B;// 读入正常价格和打折后价格}// 按照差价从大到小排序sort(a+1,a+n+1,cmp);// 前k个商品选择打折价for(inti=1;i<=k;i++){ans+=a[i].B;}// 剩余商品选择原价for(inti=k+1;i<=n;i++){ans+=a[i].A;}cout<<ans<<endl;// 输出最小总花费return0;}