建议降绿
查看原帖
建议降绿
816310
CQ_Alice楼主2024/11/12 22:15

存在比较简单的做法

考虑每个物品以原价购买,将原价作为优惠券的下限,原价和折扣价的差作为优惠券的优惠量,因此共有 n+mn+m 张优惠券。然后自然引出一个问题:存在物品 ii 和物品 jj,使得 aiaja_i \leq a_j,那么此时物品 ii 产生优惠券 (ai,aibi)(a_i,a_i-b_i),因为 aj>aia_j>a_i,所以 jj 可以使用该优惠券,虽然这是不合理的,但是显然对最后的答案没有影响,可以理解为将 iijj 分别使用的优惠券交换,容易看出,一定是可以交换的,因为 ii 可以用的优惠券 jj 也一定可以用,因为 aiaja_i \leq a_j。显然,对于其他情况都是合理的。

2024/11/12 22:15
加载中...