小红的优惠券【牛客tracker 每日一题】

小红的优惠券时间限制1秒 空间限制256M知识点贪心网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红的购物车结算金额为n nn元她手中有m mm张优惠券。第j jj张优惠券的规则为“满a j a_jaj​元立减b j b_jbj​元”即若n ≧ a j n≧a_jn≧aj​则使用该券后需支付n − b j n−b_jn−bj​元。小红至多使用一张优惠券请问最少需要支付多少元输入描述第一行输入两个整数n , m ( 1 ≦ n ≦ 10 5 ; 1 ≦ m ≦ 100 ) n,m(1≦n≦10^5; 1≦m≦100)n,m(1≦n≦105;1≦m≦100)。接下来m mm行第j jj行输入两个整数a j , b j ( 1 ≦ b j ≦ a j ≦ 10 5 ) a_j,b_j(1≦b_j≦a_j≦10^5)aj​,bj​(1≦bj​≦aj​≦105)描述第j jj张优惠券。输出描述输出一个整数表示小红使用最优策略后需支付的最少金额。示例1输入100 3 300 50 200 30 50 5输出95说明仅第三张券可用支付100 − 5 95 100−595100−595元。解题思路本题是单张优惠券最优选择的基础贪心题由于最多只能使用一张优惠券只需遍历所有券选出减免力度最大的可用方案即可。1. 贪心策略要让支付金额最少等价于在所有满足使用条件的优惠券中选取立减金额最大的那一张。如果没有可用优惠券则不使用券支付原价。使用优惠券的前提结算金额n≥ 优惠券满减门槛a_j。最优目标最大化b_j即最小化n - b_j。2. 执行步骤初始化最小值将最少支付额初始化为原价n对应不使用任何优惠券的兜底情况。遍历校验所有优惠券对每张优惠券判断是否满足满减门槛若满足则计算使用后的支付金额更新全局最小值。输出结果遍历完成后得到的最小值即为答案。3. 复杂度分析时间复杂度为O ( m ) O(m)O(m)m 最大为 100运算量极小远低于时间限制。总结核心逻辑在所有可用优惠券中选取立减金额最大的方案与原价对比取最小值即为最少支付金额。关键操作原价兜底初始化、满减门槛条件判断、遍历更新最小支付额。效率保障单重线性遍历常数级运算量运行速度极快。代码简要说明数组定义x数组存储每张优惠券的满减门槛a_jy数组存储对应的立减金额b_j。初始值设置变量mn初始化为原价n作为不使用优惠券的兜底方案。遍历更新最小值循环遍历所有优惠券若n满足满减门槛则计算使用后的支付金额若更小则更新mn。结果输出遍历结束后输出最终的最小支付金额。输入优化关闭流同步并解绑 tie提升输入读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll x[100]{0},y[100]{0};intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cinnm;for(ll i0;im;i){cinx[i]y[i];}ll mnn;for(ll i0;im;i){if(nx[i]){if(n-y[i]mn)mnn-y[i];}}coutmnendl;return0;}