首页 > 试题广场 >

支付宝消费打折

[编程题]支付宝消费打折
  • 热度指数：5547 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
众所周知，在一些消费支付的场合中，往往有“支付宝九五折”的优惠。
这天小苯来到了超市购买物品，一共有 n 种物品，每种物品只能购买一个，但有的物品支持优惠活动，有的并不支持。恰好本超市的结账是有“支付宝九五折”优惠的，小苯的支付宝余额还剩 k 元，他想知道他仅使用支付宝进行支付的话，最多能买几件物品？

输入描述:
输入包含三行。
第一行两个正整数 n, k\ (1 \leq n \leq 10^5), \ (1 \leq k \leq 10^9)。
第二行包含 n 个正整数 a_i (1 \leq a_i \leq 10^4) 表示每个物品的价格。
第三行一个长度为 n 的只含有 0 和 1 的字符串，表示每个物品是否支持优惠。（如果是 1 代表第 i 个物品支持优惠，否则不支持。）


输出描述:
输出一行一个整数表示答案。
示例1

输入

5 9
3 4 2 3 1
11101

输出

4

说明

选择买第 1，3，4，5 个物品。
算法知识视频讲解
添加回答
C++
牛客961040833号头像 牛客961040833号 
#include <iostream>
#include "bits/stdc++.h"
using namespace std;

double ival[100000];

int Algorithm(int n, double k){
    int sum=0;

    sort(ival,ival+n);//for (int i=0;i<n;i++)cout<<ival[i]<<"\n";

    int i=0;
    while (ival[i]<=k && i<n){
        k-=ival[i++];
        sum++;
    }

    return sum;
}

int main() {
    int n;
    double k;
    cin>>n>>k;
    for (int i=0;i<n;i++){
        cin>>ival[i];
    }
    string str;
    cin>>str;
    for (int i=0;i<n;i++){
        if (str[i]=='1') ival[i]*=0.95;
    }

    cout<<Algorithm(n, k);

    return 0;
}
// 64 位输出请用 printf("%lld")


被L13坑惨了，我忽略了钱数刚刚好的情况（钱数刚好等于数个商品价格相加之和），所以漏了一个等号，最后WA了8次才不得不看答案搞明白的。
标准的贪心算法，我的策略是在输入的时候同时计算折扣后的价格，然后排序，最后由小到大尝试购买商品直至钱数不够（k>ival[i]）或全部购买完毕（k==n）并计算购买的产品数量。
另外，这道题float的精度不够，需要使用double。
发表于 2025-08-22 00:31:48 回复(0)
Yui___头像 Yui___ 
def main():
    n,k = map(int,input().split())
    prices = list(map(int,input().split()))

    s = input()

    cur_index = 0
    for c in s:
        if '1' == c:
            prices[cur_index] = float(prices[cur_index] * 0.95)
        cur_index += 1
    prices.sort()

    ans = 0
    cur_index = 0
    while cur_index < n and k - prices[cur_index] >= 0:
        k -= prices[cur_index]
        ans += 1
        cur_index += 1

    print(ans)

if __name__ == '__main__':
    main()

发表于 2025-11-21 16:14:29 回复(0)
Java
BraveCoder头像 BraveCoder 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double k = in.nextDouble();  // 支付宝余额
        in.nextLine(); // 消耗换行符
        
        // 读取物品价格
        int[] price = new int[n];
        for (int i = 0; i < n; i++) {
            price[i] = in.nextInt();
        }
        in.nextLine(); // 消耗换行符
        
        // 读取折扣信息
        String discountStr = in.nextLine();
        
        // 计算最终价格
        double[] finalPrice = new double[n];
        for (int i = 0; i < n; i++) {
            if (discountStr.charAt(i) == '1') {
                // 支持优惠，九五折
                finalPrice[i] = price[i] * 0.95;
            } else {
                // 不支持优惠，原价
                finalPrice[i] = price[i];
            }
        }
        
        // 排序，优先购买便宜的物品
        Arrays.sort(finalPrice);
        
        // 计算最多能购买的数量
        int count = 0;
        double remaining = k;
        for (double p : finalPrice) {
            if (remaining >= p) {
                remaining -= p;
                count++;
            } else {
                break;
            }
        }
        
        System.out.println(count);
    }
}

发表于 2025-08-30 20:19:37 回复(0)
牛客559248288号头像 牛客559248288号
import sys

n,k = map(int,input().split())
a = list(map(int,input().split()))
s = str(input())
for i in range(n):
    if s[i] == '1':
        a[i] = round(a[i]*0.95, 3)
a.sort()

num = 0
price = 0
for p in a:
    if price+p<=k:
        price += p
        num += 1
print(num)

       
发表于 2025-12-23 23:38:13 回复(0)
代码怎么又不跑了头像 代码怎么又不跑了 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String[] command = in.nextLine().split(" ");
            int total = Integer.parseInt(command[0]);
            double totalPrice = Double.parseDouble(command[1]);
            double[] goods = Arrays.stream(in.nextLine().split(" ")).mapToDouble(Double::parseDouble).toArray();
            char[] isSub = in.nextLine().toCharArray();
            for (int i = 0; i < goods.length; i++) {
                if (isSub[i] == '1') {
                    goods[i] *= 0.95;
                }
            }

            Arrays.sort(goods);

            int count = 0;
            for (int i = 0; i < goods.length; i++) {
                if (totalPrice >= goods[i]) {
                    totalPrice -= goods[i];
                    count++;
                } else {
                    break;
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2025-12-03 16:40:52 回复(0)
Python3
大8头像 大8
greedy algorithm 
n, k = map(int, input().split())
prices = list(map(int, input().split()))
s = input()

for i in range(n):
    if s[i]=='1':
        prices[i] = round(prices[i]*0.95, 3)
prices.sort()

num = 0
price = 0
for p in prices:
    if price+p<=k:
        price += p
        num += 1
print(num)


发表于 2025-11-20 15:40:19 回复(0)
Java
Ujimatsu头像 Ujimatsu

根据打折标志，判断商品的最终价格，然后根据最终价格排序，依次获取价格最低的商品，并与预算进行比较，获取商品数量

注意货币计算，原则上不允许用double和float，只能用整数 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        long totalAmount = in.nextLong() * 100L;
        int[] goodsPrice = new int[count];
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            goodsPrice[i] = in.nextInt();
        }
        char[] alipayFlagArray = in.next().toCharArray();
        for (int i = 0; i < count; i++) {
            if ('1' == alipayFlagArray[i]) {
                list.add(goodsPrice[i] * 95L);
            } else {
                list.add(goodsPrice[i] * 100L);
            }
        }
        list.sort(null);
        long local = 0L;
        int result = 0;
        for (Long goods : list) {
            local += goods;
            if (local <= totalAmount) {
                result++;
            } else {
                break;
            }
        }
        System.out.println(result);
    }
}


发表于 2025-11-19 02:41:01 回复(0)
说谎话的小狗头像 说谎话的小狗 
n,k=list(map(int,input().split()))
n=int(n)
k=int(k)
l2=list(map(int,input().split()))
c=input()
s=0
h=0
l3=[]
for i in range(n):
    if c[i]=="1":
        l3.append(l2[i]*0.95)
    else:
        l3.append(l2[i])
l4=sorted(l3)
for j in l4:
    s+=j
    if k>s:
        h+=1
    elif k<=s:
        h=h
print(h)
#90%通过率，欢迎纠正

发表于 2025-10-12 19:34:03 回复(0)
C++
miao_nowcoder头像 miao_nowcoder 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

static bool cmp(vector<double>& a, vector<double>& b) {
    return a[1] < b[1];
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<double>> goods(n, vector<double>(2, 0));


    for (int i = 0; i < n; i++) {
        cin >> goods[i][0];
    }
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        int isdiscount = str[i] - '0';
        if (isdiscount)  goods[i][1] = goods[i][0] * 0.95;
        else  goods[i][1] = goods[i][0];
    }

    sort(goods.begin(), goods.end(), cmp);
    int result = 0;
    double money = k;  
    for (int i = 0; i < n; i++) {
        if (money >= goods[i][1]) {  
            money -= goods[i][1];
            result++;
        } else {
            break;
        }
    }
    cout << result;

}

发表于 2025-10-05 16:13:25 回复(0)
xuwzen头像 xuwzen
排序+贪心：
先计算所有物品的最终价格（包含打折优惠）；
再将价格从低到高排序；
优先购买价格最低的，依次从低到高遍历价格列表，统计购买的物品数量count，直到余额小于当前价格终止。 
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let tokens = line.split(' ');
        let n = parseInt(tokens[0]);
        let k = parseInt(tokens[1]);
        const prices = (await readline()).split(' ').map(Number);
        const cutoffs = (await readline()).split('');
        for (let i = 0; i < n; i++) {
            if (cutoffs[i] === '1') {
                prices[i] *= 0.95;
            }
        }
        prices.sort((a, b) => a - b);

        let count = 0;
        for (let price of prices) {
            if (price > k) {
                break;
            }
            k -= price;
            count++;
        }

        console.log(count);
    }
}()


发表于 2025-09-23 11:19:08 回复(0)
我不喝牛奶头像 我不喝牛奶 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            String c = in.nextLine();
            String[] bArr = b.split(" ");
            //初始化商品列表
            List<Good> goods = new ArrayList<>();
            for (int i = 0; i < bArr.length; i++ ){
                int price = Integer.parseInt(bArr[i]) ;
                char discount = c.charAt(i);
                double discountPrice = 0.0;
                if (discount == '0'){
                    discountPrice = price;
                } else if (discount == '1'){
                    discountPrice = price * 0.95;
                }
                goods.add(new Good(i,price,discountPrice));
            }
            //按照折扣后的价格排序，升序 // 按折扣后价格升序排序（核心贪心策略）
            goods.sort(Comparator.comparingDouble(Good::getDiscountPrice));
            String[] aArr = a.split(" ");
            double money = Double.parseDouble(aArr[1]);
            int max = 0;
            int bLen = bArr.length;
            double sum = 0.0;
            final double EPS = 1e-8; // 精度误差允许范围
            //进行计算，从最便宜的进行加和
            for (int i = 0; i < bLen; i++){
                sum += goods.get(i).getDiscountPrice();
                if (sum <= money + EPS){
                    //没有超过余额则能购买
                    max++;
                } else {
                    //超过余额则不能购买，直接退出循环
                    break;
                }
            }
            System.out.println(max);
        }
    }
}
//商品
class Good{
    int id;
    int price;
    //存储打折后的价格
    double discountPrice;
    public int getId(){
        return this.id;
    }
    public int getPrice(){
        return this.price;
    }
    public double getDiscountPrice(){
        return this.discountPrice;
    }
    public Good(int id ,int price , double discountPrice){
        this.id=id;
        this.price=price;
        this.discountPrice=discountPrice;
    }
}

发表于 2025-09-16 00:55:12 回复(0)
Java
清浅QAQ头像 清浅QAQ
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int k = in.nextInt();
        Double[] arr = new Double[n];
        for(int i = 0; i < n; i++){
            arr[i] = in.nextDouble();
        }
        in.nextLine();
        String str = in.nextLine();
        for(int i = 0; i < n; i++){
            arr[i] = str.charAt(i) == '1' ? arr[i] * 0.95 : arr[i];
        }
        Arrays.sort(arr);
        int num = 0;
        double sum = 0;
        while(num < n){
            if(sum + arr[num] > k){
                break;
            }else{
                sum += arr[num];
                num++;
            }
        }
        System.out.println(num);
    }
}
发表于 2025-09-04 23:58:20 回复(0)
Python 3
忧伤的双曲线头像 忧伤的双曲线
n,k = map(int,input().split())
a = list(map(int,input().split()))
s = input()

for i in range(n):
    if s[i]=='1':
        a[i] *= 0.95

sorted_a = sorted(a)
summ = 0
for j in range(n):
    summ += sorted_a[j]
    if summ>k:
        print(j)
        break
if summ<=k:
    print(n)
发表于 2025-08-25 23:50:00 回复(0)
学习小生头像 学习小生 
n,k = map(int,input().split())
values = list(map(int,input().split()))
zhekou = list(input())
finally_values = []
for i in range(n):
    if zhekou[i] == "1":
        finally_values.append(values[i]*0.95)
    else:
        finally_values.append(values[i])
sorted_values = sorted(finally_values)
sum_value = 0
count = 0
for value in sorted_values:
    sum_value += value
    if sum_value > k:
        break
    count += 1
print(count)

发表于 2025-08-23 22:29:15 回复(0)
1900201910072158499头像 1900201910072158499
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayList<Double> list = new ArrayList<>();
        ArrayList<Double> list2 = new ArrayList<>();

        double n = in.nextDouble();
        double k = in.nextDouble();
        for (int i = 0; i < n; i++) {
            list.add(in.nextDouble());
        }
        char[] chars = in.next().toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '1') list2.add(i, list.get(i) * 0.95);
            else list2.add(i, list.get(i));
        }
        Collections.sort(list2);
        int count = 0;
        for (Double v : list2) {
            if (k - v >= 0) {
                k = k - v;
                count++;
            } else {
                break;
            }
        }
        System.out.println(count);

    }
}

发表于 2025-08-14 14:38:15 回复(0)
Python
冷飒5611头像 冷飒5611
import sys

n,k = map(int,input().split())
prince = list(map(int,input().split()))

flag2 = input()
flag = []
for i in flag2:
    flag.append(int(i))
prince2 = []
for i,j in enumerate(prince):
    val = j*0.95 if flag[i] else j
    prince2.append(val)
prince2.sort()
ans = 0
for i in prince2:
    k-=i
    if k>=0:
        ans+=1
    else:
        break
print(ans)


发表于 2025-07-29 11:12:59 回复(0)
上岸保佑头像 上岸保佑 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long k = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        String s = in.next();
                //小数乘以100，防止精度丢失
        long[] cost = new long[n];
        for(int i = 0; i < n; i++) {
            if(s.charAt(i) == '1') { 
                cost[i] = a[i] * 95L;
            } else {
                cost[i] = a[i] * 100L;
            }
        }
        Arrays.sort(cost);
        long total = 0;
        int count = 0;
        long max = k * 100;
        for(int i = 0; i < n; i++) {
            if(total + cost[i] > max) {
                break;
            }
            total += cost[i];
            count++;
        }
        System.out.print(count);
    }
}


发表于 2025-04-01 16:55:19 回复(1)
有礼貌的山羊追赶太阳头像 有礼貌的山羊追赶太阳 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double k = in.nextDouble();        
        int i = 0;
        double [] a = new double[n];
        while(i<n){
            a[i++] = in.nextInt();
        }
        i = n - 1;
        in.nextLine();        
        String s = in.nextLine();
        while(i>=0){
            if(s.charAt(i) == 1)
                a[i] *= 0.95;
            i -= 1;
        }
        Arrays.sort(a);
        int ans = 0;
        for(i =0;i<n;++i){
            k -= a[i];
            if(k <0)
                break;
            ans += 1;
        }
        System.out.println(ans);
    }
}
这题应该要用大数乘法了，好像是用double会丢失精度，导致我的答案偏差了一些，过不了几个样例。
发表于 2025-03-28 16:47:10 回复(1)
提交观点

问题信息

贪心 排序
难度：
18条回答 542浏览

热门推荐

相关试题

支付宝消费打折

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号