支付宝消费打折

一、 核心解题思路（为什么这么做？）

这道题的目标是：用有限的钱（预算 k），买尽可能多的物品。

想象一下你在超市，手里只有 100 块钱，你想在购物车里塞尽可能多的东西，你会怎么做？ 你一定会先挑最便宜的买，对不对？便宜的买完了，再买稍微贵一点的，直到钱花光为止。这就是计算机算法中非常著名的“贪心算法（Greedy Algorithm）”——每一步都做出当前看起来最划算的选择。

本题的特殊技巧：避免小数计算。 题目说有“九五折（乘以 0.95）”。在 C++ 中，如果你用小数（double或float）去算钱，可能会因为计算机底层的精度问题，导致0.95变成了0.9499999，最后算错。 为了避开小数，我们把所有的钱、商品价格全都放大 100 倍。

• 原价打九五折：原本是价格 * 0.95，现在变成价格 * 95。

• 不打折：原本是价格 * 1，现在变成价格 * 100。

• 你的总预算k：也跟着放大，变成k * 100。 这样，全程都只计算整数，绝对不会出错！

二、 扫盲：你必须要懂的 C++ 工具（函数/语法）

在这里，首先要对你提出的问题做一个非常重要的小纠正： 在代码中，cost并不是一个函数，而是一个变量的名字，它的真正身份是 C++ 里的vector（动态数组）。

1. 为什么用vector？（你误以为的 cost 函数）

• 是什么： vector中文叫“向量”或“动态数组”，你可以把它当成一个“可以伸缩的抽屉”。

• 为什么用它： 在传统的 C 语言里，数组必须提前规定好大小，比如int arr[100];。但是这道题里，物品数量n是用户临时输入的，没法提前规定。vector允许我们根据用户输入的n，立刻生成一个恰好有n个格子的数组。

• 怎么用： 语法是vector<数据类型> 变量名(大小);。代码里的vector<long long> cost(n);意思就是：给我创建一个名叫cost的动态数组，里面专门装long long类型的超大整数，并且给我准备n个格子。

2. 为什么用sort函数？

• 是什么： 它是 C++ 标准库<algorithm>提供的一个超级排序工具。

• 为什么用它： 我们前面说了，买东西要“从最便宜的开始挑”。也就是说，我们需要把算好折扣后的物品价格，从小到大排个序。如果你自己写排序代码（比如冒泡排序），要写好几行循环，而且运行速度很慢。直接用 C++ 写好的sort函数，一行代码搞定，且速度极快。

• 怎么用： 语法是sort(数组起点, 数组终点);。代码里的sort(cost.begin(), cost.end());意思就是：把cost这个数组，从头（begin）到尾（end），按从小到大的顺序排好。

3. 为什么用string？

• 是什么： 字符串，用来装一长串字符（比如 "11101"）。

• 为什么用它： 题目输入了一串由0和1组成的字符，代表打不打折。用string接收最方便，它可以通过s[i]的方式，直接像查字典一样查出第i个物品打不打折。

4. 为什么用long long而不是int？

• 是什么： int和long long都是整数。但int的“容量”比较小（最大只能装大概 21 亿）。

• 为什么用它： 题目说预算最大是 10的9次方（10亿）。我们为了不出现小数，把预算放大了 100 倍，这就变成了 10的11次方（1000亿）。这已经超出了int的承受范围，如果不换成“容量更大”的long long，程序就会“撑爆（溢出）”报错。

  好的，我来帮你逐行详细解释这段 C++ 代码，既讲解代码逻辑思路，也讲解每个函数、语法和用法，适合刚学习 C++ 的学生理解。

  ---

  题目理解

  • 我们有n件物品，每件物品只能买一次。

  • 有些物品支持支付宝 95 折优惠，有些不支持。

  • 已知小苯的支付宝余额k元，问最多能买多少件物品。

  • 贪心策略：总是先买价格最便宜的物品，这样能买的件数最多。

  ---

  代码逐行解释

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

  1. #include <iostream>

     • 引入输入输出流库，允许使用cin（标准输入）和cout（标准输出）。

     • 例：cin >> n;可以从键盘输入一个整数n，cout << n;可以输出整数n。

  2. #include <vector>

     • 引入vector容器，类似于动态数组，可以存放任意数量的元素，大小可动态增长。

     • 用在这里保存每个物品的价格。

  3. #include <algorithm>

     • 引入 STL（标准模板库）算法函数，例如sort()排序、max()求最大值等。

     • 在这里主要用sort()来对物品价格排序，从小到大。

  4. #include <string>

     • 引入字符串类std::string，方便存储和操作一行字符（例如'1'和'0'的优惠信息字符串）。

  ---

  using namespace std;

  • 使用标准命名空间std，这样就不用每次写std::vector或std::cout，直接写vector、cout就行。

  • 初学者注意：虽然方便，但在大型项目中，直接使用using namespace std;可能会造成名字冲突。

  ---

  int main() {

  • C++ 程序的入口函数，程序从这里开始执行。

  • int表示返回类型，通常返回 0 表示程序正常结束。

  ---

  int n;
      long long k; // 预算最大 10^9，放大100倍后会超出int范围，必须用 long long

  1. int n;

     • 用于存储物品数量n。

     • int是整数类型，占 4 字节，范围大约-2*10^9到2*10^9。

  2. long long k;

     • 用于存储支付宝余额k。

     • 这里用long long（8 字节整数）是因为后面要把金额放大 100 倍计算折扣，放大后可能超过int的范围。

     • long long范围大约 ±9*10^18，足够存放。

  ---

  // 1. 读取物品数量 n 和初始预算 k
      if (!(cin >> n >> k)) return 0;

  1. cin >> n >> k

     • 从标准输入读取两个整数，分别赋值给n和k。

     • >>是输入流操作符，把用户输入的数据存入变量。

  2. if (!(...)) return 0;

     • 判断输入是否成功，如果输入失败（例如用户没有输入数字），直接退出程序。

     • !表示逻辑非，cin >> n >> k成功返回true，失败返回false。

  ---

  // 2. 读取每个物品的原价
      vector<long long> cost(n);

  1. vector<long long> cost(n);

     • 声明一个vector容器，存储n个long long类型的元素。

     • 初始元素值会默认是 0。

     • 为什么用vector：因为n可能很大（≤ 10^5），动态数组比普通数组更安全，且可以方便使用 STL 函数。

  ---

  for (int i = 0; i < n; i++) {
          cin >> cost[i];
      }

  1. for (int i = 0; i < n; i++)

     • 循环n次，用于逐个读取物品价格。

     • i从 0 到 n-1，对应vector的下标。

  2. cin >> cost[i];

     • 将每件物品的价格读入vector的对应位置。

     • cost[i]表示第i个物品的价格。

  ---

  // 3. 读取打折情况字符串
      string s;
      cin >> s;

  1. string s;

     • 声明一个字符串变量s。

  2. cin >> s;

     • 从输入读取一行字符（长度为n），每个字符是'0'或'1'，表示对应物品是否支持 95 折。

     • '1'→ 支持折扣

     • '0'→ 不支持折扣

  ---

  // 4. 计算每个物品的实际花费（放大100倍）
      for (int i = 0; i < n; i++) {
          if (s[i] == '1') {
              cost[i] = cost[i] * 95;  // 打九五折
          } else {
              cost[i] = cost[i] * 100; // 不打折
          }
      }

  1. 循环遍历每件物品

     • i从 0 到 n-1，对应每件物品。

  2. 判断折扣

     • s[i] == '1'→ 支持折扣

     • 使用cost[i] = cost[i] * 95;

       • 这里直接将价格乘以 95，把折扣后的价格按百分比放大 100 倍表示，例如 3 元 → 3*95=285。

       • 为什么放大 100 倍？因为 C++ 默认整型除***舍弃小数，放大后可以用整数避免精度问题。

  3. 不打折

     • cost[i] = cost[i] * 100;→ 不打折，价格也放大 100 倍方便后续计算。

  ---

  // 5. 贪心策略：按实际花费从小到大排序
      sort(cost.begin(), cost.end());

  1. sort(cost.begin(), cost.end());

     • sort是 STL 提供的排序函数，#include <algorithm>才能用。

     • cost.begin()→ 指向vector第一个元素的迭代器

     • cost.end()→ 指向vector最后一个元素之后的迭代器

     • 整体意思：把cost中的价格从小到大排序。

     • 为什么排序：贪心策略，总是先买便宜的物品，这样买的件数最多。

  ---

  k = k * 100; // 预算也放大100倍

  • 将支付宝余额也放大 100 倍，与物品价格单位统一，避免浮点运算。

  ---

  int count = 0;

  • 声明一个计数器count，记录最多能买的物品件数。

  • 初始值为 0。

  ---

  for (int i = 0; i < n; i++) {
          if (k >= cost[i]) { // 如果钱还够买当前的物品
              k -= cost[i];   // 扣除花费
              count++;        // 购买数量加1
          } else {
              break;          // 钱不够了，后面的更贵，直接结束
          }
      }

  1. 循环遍历排序后的物品价格

     • i从 0 到 n-1

     • 因为已经按从便宜到贵排序，贪心策略保证先买最便宜的。

  2. 判断是否能买

     • if (k >= cost[i])→ 钱够买当前物品

  3. 扣钱和计数

     • k -= cost[i];→ 扣除当前物品价格

     • count++;→ 成功买一件物品，计数加 1

  4. 钱不够

     • else break;→ 由于价格已经排序，后面更贵，直接结束循环。

  ---

  // 7. 输出最多能买的件数
      cout << count << endl;

  • cout << count << endl;

    • cout输出到控制台

    • endl换行并刷新缓冲区

    • 输出最终结果：最多能买的物品件数。

  ---

  return 0;
  }

  • 程序结束，返回 0 表示正常退出。

  ---

  总结关键点

  1. 用vector<long long> → 保存物品价格，方便动态大小和使用 STL 函数。

  2. 用string → 存折扣信息'1'/'0'，方便判断折扣。

  3. 放大 100 倍 → 避免浮点数带来的精度问题。

  4. sort()函数 → STL 排序，贪心策略：先买便宜的。

  5. 循环贪心买物品 → 用if-else判断预算够不够，保证买最多件数。

  ---

  如果你愿意，我可以帮你画一张 流程图 + 代码流程对应表，让初学者更直观理解整个逻辑和每个函数的作用。

  你希望我画吗？

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()

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);//缩短运行时间
    cin.tie(nullptr);//缩短运行时间

    long long n, k;
    cin >> n >> k;
    vector<long long> price(n);
    for ( int i = 0; i < n; ++i) {
        cin >> price[i];
    }
    string disc;
    cin >> disc;
    for (int i = 0; i < n; ++i) {
        if (disc[i] == '1')
            price[i] = price[i] * 95;//先化为分再打95折
        else
            price[i] = price[i] * 100; //化为分
    }

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

    k = k * 100;
    int cnt = 0;
    for ( auto p : price) {
        if ( p <= k) {
            k = k - p;
            ++cnt;
        } else {
            break;
        }
    }
    cout << cnt << endl;
    return 0;

}

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);
    }
}

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int n,k;
    cin>>n>>k;
    vector<double>a;
    string s;
    for(int i=0;i<n;i++){
    	int x;
    	cin>>x;
    	a.push_back(x);
    }
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            a[i]*=0.95;
        }
    }
    sort(a.begin(),a.end());    
    double sum=0,cnt=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
        if(sum<=k)cnt++;else break;
    }
    cout<<cnt;
    return 0;
}

#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<string>
int main() {
    vector<double>v_price;
   int n,k;
   cin>>n>>k;
   for(int i=0;i<n;i++){
       double price;
       cin>>price;
       v_price.push_back(price);
   }
   string s;
   cin>>s;
   for(int i=0;i<s.size();i++){
      if(s[i]=='1'){
          v_price[i]=v_price[i]*0.95;
      }
   }
   sort(v_price.begin(),v_price.end());
   double sumprice=0; //易错：用int定义+double丢精度报错 
   int count=0;
   for(int i=0;i<n;i++){
      if(sumprice+v_price[i]<=k){
         sumprice+=v_price[i];
         count++;
      }
      else{
        break;
      }
   }
   cout<<count;
   
}
// 64 位输出请用 printf("%lld")

# 分别定义两个正整数，分别表示物品的个数n和支付宝余额k
n,k = map(int,input().split())
# 建立一个列表表示物品的价格
a = list(map(int,input().split()))
# 建立一个仅包含0/1的列表，表示是否可以使用优惠卷
yes_no = list(map(str,input()))
# 定义一个列表用于存储可以优惠的商品优惠后的价格和不可以优惠商品不优惠的价格
list1 = []
for i in range(n):
    if yes_no[i] == '1':
        list1.append(a[i] * 0.95)
    else:
        list1.append(a[i])
# 进行排序
list1.sort()
count1 = 0
# 用拥有的钱减去排序后商品的价格 
for v in list1:
    if k >= v:
        k -= v
        count1 += 1
print(count1)

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);
        }
    }
}

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

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);
    }
}

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%通过率，欢迎纠正

#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;

}