支付宝消费打折【牛客tracker 每日一题】

支付宝消费打折时间限制1秒 空间限制256M知识点贪心排序网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述众所周知在一些消费支付的场合中往往有“支付宝九五折”的优惠。这天小苯来到了超市购买物品一共有n nn种物品每种物品只能购买一个但有的物品支持优惠活动有的并不支持。恰好本超市的结账是有“支付宝九五折”优惠的小苯的支付宝余额还剩k kk元他想知道他仅使用支付宝进行支付的话最多能买几件物品输入描述输入包含三行。第一行两个正整数n , k ( 1 ≤ n ≤ 10 5 ) , ( 1 ≤ k ≤ 10 9 ) n,k (1≤n≤10^5), (1≤k≤10^9)n,k(1≤n≤105),(1≤k≤109)。第二行包含n nn个正整数a i ( 1 ≤ a i ≤ 10 4 ) a_i(1≤a_i≤10^4)ai​(1≤ai​≤104)表示每个物品的价格。第三行一个长度为n nn的只含有0 00和1 11的字符串表示每个物品是否支持优惠。如果是1 11代表第i ii个物品支持优惠否则不支持。输出描述输出一行一个整数表示答案。示例1输入5 9 3 4 2 3 1 11101输出4说明选择买第1 3 4 5 13451345个物品。解题思路本题核心是贪心算法求解预算内可购买的最大物品数量遵循优先选择实际花费最低物品的最优策略。为避免浮点数精度误差将九五折优惠转化为整数运算支持优惠的物品价格×95不支持的×100同时总余额×100统一计算单位。将所有物品的实际支付代价从小到大排序依次尝试购买每买一件扣除对应代价直到余额不足以购买下一件物品最终统计购买的总数量。该贪心策略能保证数量最大化算法时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)完美适配n ≤ 10 5 n \le 10^5n≤105的大数据约束。总结核心逻辑贪心选择实际花费最低的物品整数运算彻底规避浮点数精度问题。关键操作价格整数化转换、排序筛选低价物品、顺序累加统计最大数量。效率保障排序线性遍历计算高效轻松处理十万级数据量。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cinnk;ll arr[100005];for(ll i1;in;i)cinarr[i];string str;cinstr;for(ll i1;in;i){if(str[i-1]1)arr[i]*95;elsearr[i]*100;}sort(arr1,arrn1);k*100;ll ans0;if(karr[1]){for(ll i1;in;i){k-arr[i];if(k0)ans;elsebreak;}}coutansendl;return0;}