支付宝消费打折

思路

拿到这道题，先想清楚目标是什么？你有 n 件物品，每件只能买一个，有的能用支付宝打九五折，有的不能。你手上有 m 元余额，问最多能买几件？

那既然要买尽可能多的物品，直觉告诉你应该怎么做？——当然是先买便宜的。贵的往后排，能塞几个塞几个。

关键点：怎么算每件物品的实际花费？

  • 支持优惠的物品（标记为 1）：实际花费 = 原价 × 0.95
  • 不支持优惠的物品（标记为 0）：实际花费 = 原价

然后把所有物品按实际花费从小到大排序，贪心地从最便宜的开始买，直到余额不够为止。

一个细节：浮点数精度问题

0.95 是个小数，直接用浮点运算可能有精度问题。怎么避免？把所有数都乘以 20，这样：

  • 不打折的物品花费 = 原价 × 20
  • 打折的物品花费 = 原价 × 19（因为 0.95 × 20 = 19）
  • 余额也变成 m × 20

这样全程整数运算，干净利落。

代码

#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]);
    string s;
    cin >> s;
    // 乘以 20 避免浮点，打折 ×19，不打折 ×20
    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 cnt = 0;
    for(int i = 0; i < n; i++){
        if(budget >= cost[i]){
            budget -= cost[i];
            cnt++;
        } else break;
    }
    printf("%d\n", cnt);
    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();
        // 乘以 20 避免浮点，打折 ×19，不打折 ×20
        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 cnt = 0;
        for (int i = 0; i < n; i++) {
            if (budget >= cost[i]) {
                budget -= cost[i];
                cnt++;
            } else break;
        }
        System.out.println(cnt);
    }
}

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
s = input().strip()

# 乘以 20 避免浮点，打折 ×19，不打折 ×20
cost = []
for i in range(n):
    if s[i] == '1':
        cost.append(a[i] * 19)
    else:
        cost.append(a[i] * 20)

cost.sort()
budget = m * 20
cnt = 0
for c in cost:
    if budget >= c:
        budget -= c
        cnt += 1
    else:
        break
print(cnt)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    const s = lines[2].trim();
    // 乘以 20 避免浮点，打折 ×19，不打折 ×20
    const cost = [];
    for (let i = 0; i < n; i++) {
        if (s[i] === '1') cost.push(a[i] * 19);
        else cost.push(a[i] * 20);
    }
    cost.sort((a, b) => a - b);
    let budget = m * 20;
    let cnt = 0;
    for (let i = 0; i < n; i++) {
        if (budget >= cost[i]) {
            budget -= cost[i];
            cnt++;
        } else break;
    }
    console.log(cnt);
});

复杂度分析

  • 时间复杂度: ，瓶颈在排序
  • 空间复杂度: ，存每件物品的实际花费

总结

这道题本质就是贪心排序：算出每件物品的实际花费，排个序，从便宜的开始买。唯一值得注意的是九五折带来的浮点精度问题，全部乘 20 转成整数就搞定了。排序贪心是很经典的套路，遇到"最多能选几个"这类问题，优先往这个方向想。