题解 | #支付宝消费打折#

题目链接

题目描述

小苯在超市购买 $N$ 种物品，每种物品只能购买一个。他的支付宝余额为 $X$ 元。部分物品支持“九五折”优惠。给定每种物品的价格以及是否支持优惠，请问他仅用支付宝支付，最多能买几件物品？

输入描述

第一行两个正整数 $N, X$ 。第二行包含 $N$ 个正整数 $p_i$ ，表示第 $i$ 个物品的价格。第三行一个长度为 $N$ 的字符串，由 '0' 和 '1' 组成。如果第 $i$ 个字符是 '1'，代表第 $i$ 个物品支持优惠，否则不支持。

输出描述

输出一行一个整数，表示最多能购买的物品数量。

样例

输入

5 9
3 4 2 3 1
11101

输出

解题思路

本题的目标是在有限的预算内，购买尽可能多的物品。这是一个经典的贪心问题。

贪心策略：要想购买数量最多，应该始终优先选择当前能买得起的最便宜的物品。

处理折扣： “九五折”意味着价格乘以 0.95。直接使用浮点数进行计算可能会引入精度问题。一个稳妥的技巧是将所有金额放大100倍，从而将计算全程转为整数：

支付宝余额 $X$ 变为 $X \cdot 100$ 。
不支持优惠的物品价格 $p_i$ 变为 $p_i \cdot 100$ 。
支持优惠的物品价格 $p_i$ 变为 $p_i \cdot 95$ 。

算法步骤：

读入物品数量 $N$ 和余额 $X$ 。
读入 $N$ 个物品的原价和优惠信息字符串。
创建一个新的数组 actual_costs，用于存储每个物品的实际购买价格（放大100倍后）。
遍历 $N$ 个物品：
- 如果第 $i$ 个物品支持优惠，其真实成本为 $p_i \cdot 95$ 。
- 否则，其真实成本为 $p_i \cdot 100$ 。
- 将计算出的实际成本存入 actual_costs 数组。
对 actual_costs 数组进行升序排序。
将余额 $X$ 乘以 100，得到整数表示的总预算 $budget = X \cdot 100$ 。
初始化购买物品数量 $count = 0$ 。
遍历排序后的 actual_costs 数组：
- 对于每个物品的实际成本 $cost$ ，如果 $budget \ge cost$ ，则购买该物品：
  - $budget = budget - cost$
  - $count = count + 1$
- 如果 $budget < cost$ ，则无法购买当前及更贵的物品，直接结束遍历。
输出最终的 $count$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n;
    long long x;
    cin >> n >> x;

    vector<long long> prices(n);
    for (int i = 0; i < n; ++i) {
        cin >> prices[i];
    }
    string discounts;
    cin >> discounts;

    vector<long long> actual_costs;
    for (int i = 0; i < n; ++i) {
        if (discounts[i] == '1') {
            actual_costs.push_back(prices[i] * 95);
        } else {
            actual_costs.push_back(prices[i] * 100);
        }
    }

    sort(actual_costs.begin(), actual_costs.end());

    long long budget = x * 100;
    int count = 0;

    for (long long cost : actual_costs) {
        if (budget >= cost) {
            budget -= cost;
            count++;
        } else {
            break;
        }
    }

    cout << count << '\n';

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();

        long[] prices = new long[n];
        for (int i = 0; i < n; i++) {
            prices[i] = sc.nextLong();
        }
        String discounts = sc.next();

        long[] actual_costs = new long[n];
        for (int i = 0; i < n; i++) {
            if (discounts.charAt(i) == '1') {
                actual_costs[i] = prices[i] * 95;
            } else {
                actual_costs[i] = prices[i] * 100;
            }
        }

        Arrays.sort(actual_costs);

        long budget = x * 100;
        int count = 0;

        for (long cost : actual_costs) {
            if (budget >= cost) {
                budget -= cost;
                count++;
            } else {
                break;
            }
        }

        System.out.println(count);
    }
}

# -*- coding: utf-8 -*-

n, x = map(int, input().split())
prices = list(map(int, input().split()))
discounts = input()

actual_costs = []
for i in range(n):
    if discounts[i] == '1':
        actual_costs.append(prices[i] * 95)
    else:
        actual_costs.append(prices[i] * 100)

actual_costs.sort()

budget = x * 100
count = 0

for cost in actual_costs:
    if budget >= cost:
        budget -= cost
        count += 1
    else:
        break

print(count)

算法及复杂度

算法：贪心、排序
时间复杂度： $O(N \cdot \log N)$ ，其中 $N$ 是物品数量。主要开销来自于对物品的实际购买成本进行排序。
空间复杂度： $O(N)$ ，用于存储 $N$ 个物品的原价和实际成本。