支付宝消费打折

[题目链接](https://www.nowcoder.com/practice/f8997c9b82714f058e12433a32614993)

思路

本题要求在支付宝余额有限的情况下，最多能买几件物品。部分物品享受九五折优惠，部分不享受。

贪心策略

要买尽可能多的物品，自然应该优先购买实际花费最少的物品。因此：

计算每件物品的实际花费：若支持优惠，实际价格为 $a_i \times 0.95$ ；否则为 $a_i$ 。
按实际花费从小到大排序。
依次购买，直到余额不足。

避免浮点误差

直接乘以 0.95 会引入浮点误差。注意到 $0.95 = \frac{19}{20}$ ，可以将所有价格和预算统一乘以 20：

支持优惠的物品：实际花费为 $a_i \times 19$
不支持优惠的物品：实际花费为 $a_i \times 20$
预算变为 $m \times 20$

这样全程只用整数运算，完全避免了精度问题。

样例验证

5 件物品，预算 9 元，价格 $[3, 4, 2, 3, 1]$ ，优惠标记 11101。

乘以 20 后的实际花费： $[57, 76, 38, 60, 19]$ ，排序后为 $[19, 38, 57, 60, 76]$ 。

预算 $9 \times 20 = 180$ 。依次购买： $19 + 38 + 57 + 60 = 174 \leq 180$ ，第 5 件再加 76 超出预算。答案为 4。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long m;
    scanf("%d%lld", &n, &m);
    vector<int> a(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    char s[200005];
    scanf("%s", s);
    vector<long long> cost(n);
    for(int i = 0; i < n; i++){
        if(s[i] == '1') cost[i] = (long long)a[i] * 19;
        else cost[i] = (long long)a[i] * 20;
    }
    sort(cost.begin(), cost.end());
    long long budget = m * 20;
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(budget >= cost[i]){
            budget -= cost[i];
            ans++;
        } else break;
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        String s = sc.next();
        long[] cost = new long[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') cost[i] = (long) a[i] * 19;
            else cost[i] = (long) a[i] * 20;
        }
        Arrays.sort(cost);
        long budget = m * 20;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (budget >= cost[i]) {
                budget -= cost[i];
                ans++;
            } else break;
        }
        System.out.println(ans);
    }
}

复杂度分析

时间复杂度： $O(n \log n)$ ，瓶颈在排序。
空间复杂度： $O(n)$ ，存储每件物品的实际花费。