笔试时间：2024年03月16日

历史笔试传送门：2023秋招笔试合集

第一题

题目：支付宝消费打折

众所周知，在一些消费支付的场合中，往往有“支付宝九五折”的优惠。这天小苯来到了超市购买物品，一共有n种物品，每种物品只能购买一个，但有的物品支持优惠活动，有的并不支持。恰好本超市的结账是有“支付宝九五折”优惠的，小苯的支付宝余额还剩k元，他想知道他仅使用支付宝进行支付的话，最多能买几件物品？

输入描述

输入包含三行。

第一行两个正整数n,k(1<=n<=10^5),(1<=k<=10^9)。

第二行包含n个正整数ai(1<=ai<=10^4)表示每个物品的价格。

第三行一个长度为n的只含有0和1的字符串，表示每个物品是否支持优惠。（如果1代表第i个物品支持优惠，否则不支持。）

输出描述

输出一行一个整数表示答案。

样例输入

5 9

3 4 2 3 1

11101

样例输出

4

说明

选择买第 1，3，4，5 个物品。

参考题解

贪心。将所有的商品按照是否可打折的数值进行排序，然后从小到大取即可。因为每个物品没有权值，所以不需要用背包解决。

C++：[此代码未进行大量数据的测试，仅供参考]

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

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> prices[i];
    }

    std::string is_off;
    std::cin >> is_off;

    std::vector<double> off_prices;
    for (int i = 0; i < n; ++i) {
        off_prices.push_back(prices[i] * (is_off[i] == '0' ? 1.0 : 0.95));
    }
    
    sort(off_prices.begin(), off_prices.end());
    
    int ans = 0;
    double cost = 0;
    for (double p : off_prices) {
        if (cost + p > k) break;
        cost += p;
        ans++;
    }

    std::cout << ans << std::endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.nextLine(); // Consume newline

        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = scanner.nextInt();
        }

        scanner.nextLine(); // Consume newline
        String isOff = scanner.next();

        ArrayList<Double> offPrices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            offPrices.add(prices[i] * (isOff.charAt(i) == '0' ? 1.0 : 0.95));
        }

        Collections.sort(offPrices);

        int ans = 0;
        double cost = 0;
        for (double p : offPrices) {
            if (cost + p > k) break;
            cost += p;
            ans++;
        }

        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n,k = map(int, input().split())
prices = [int(c) for c in input().split()]
is_off = [c for c in input()]

off_prices = [prices[i] * (1 if is_off[i]=='0' else 0.95) for i in range(n)]
off_prices.sort()
ans = 0
cost = 0
for p in off_prices:
    if cost + p > k:break
    cost += p
    ans += 1

print(ans)

第二题

题目：小红切字符串

小红定义一个字符串的权值是：字符串辅音数量和元音数量的差的绝对值。例如，"arcaea"的权值是 2，因为有 4 个元音，2 个辅音，权值为|4-2|=2。现在小红拿到了一个字符串，她想把这个字符串切成两个非空字符串，需要满足两个字符串的权值相等。小红想知道，有多少种不同的切割方式？我们定义，元音有"aeiou"这五种，其余字母均为辅音。

输入描述

一个仅包含小写字母的字符串，长度不超过 200000。

输出描述

小红的切割方案数。

样例输入

arcaea

样例输出

2

说明

方案 1："a"和"rcaea"，权值均为 1。

方案 2："arcae"和"a"，权值均为 1。

参考题解

枚举所有的分割的可能，使用前缀和计算出左右两个字符串的权值即可。

C++：[此