✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

春秋招合集 -> 互联网必备刷题宝典🔗

拼多多

题目一：神奇公园的福娃占卜

1️⃣：遍历字符串，统计连续'1'的最大长度

2️⃣：判断最大连续长度是否等于9

难度：简单

这道题目要求判断字符串中最长连续'1'的数量是否恰好等于9。通过一次遍历，使用计数器记录当前连续'1'的数量，并更新最大连续数量，最后判断是否等于9即可。是一道典型的字符串处理问题，时间复杂度为O(n)。

题目二：糖果店的优惠兑换计划

1️⃣：根据公式计算每位顾客的免费额度

2️⃣：判断总免费额度是否足够，不足则计算所需兑换券数量

难度：中等

这道题涉及优惠兑换规则的理解和数学计算。关键是分析出每位顾客有一个"免费额度"，可以不用兑换券就能兑换一定数量的糖果。通过计算总免费额度，再根据剩余糖果数量计算所需兑换券数，可以高效解决问题。需要注意大数处理，时间复杂度为O(T)。

题目三：数字重排最大化问题

1️⃣：分析序列长度关系，简化特殊情况

2️⃣：贪心构造解，从高位到低位尝试匹配

3️⃣：必要时回溯调整前面的选择

难度：中等偏难

这道题要求将一个数字序列重排，使其尽可能大但又小于另一个给定数字。解法采用贪心策略，从高位到低位构造结果。需要处理序列长度不同的特殊情况，并在构造过程中适时回溯，是一道考验思维能力和实现技巧的问题。时间复杂度为O(n)。

题目四：优惠券最优分配问题

1️⃣：对商品和优惠券按价格/门槛排序

2️⃣：使用最大堆维护当前可用的优惠券

3️⃣：贪心选择策略，为每个商品分配减免最大的可用优惠券

难度：中等

这道题目是典型的贪心算法应用场景。通过对商品和优惠券排序，并利用优先队列（最大堆）来存储可用的优惠券，可以高效地为每个商品分配最优的优惠券。理解为什么贪心策略在这个问题中是最优的是解题的关键。时间复杂度为O((n+m)log(m))。

01. 神奇公园的福娃占卜

问题描述

小基在一个神奇的公园里发现了一条特殊的小径，小径上排列着一群可爱的福娃玩偶。这条小径有 个位置按顺序排列，每个位置最多可以放置一个福娃。小径的状态可以用一个仅包含 和 的字符串 来表示，其中 等于 表示第 个位置上放着福娃，等于 则表示该位置空着。

根据公园管理员的说法，如果小径上连续的福娃数量（即连续的 的数量）恰好等于 ，那么这条小径就具有神奇的力量，被认为是"幸运小径"。小基想知道眼前的小径是否是幸运的。如果是幸运小径，请输出 ，否则输出 。

输入格式

第一行包含一个正整数 ，代表测试数据的组数。

对于每组测试数据，分别有两行：

第一行包含一个正整数 ，表示小径的长度。

第二行包含一个仅由 和 组成、长度为 的字符串 ，其中 表示第 个位置是否有福娃，等于 时有，等于 时没有。

输出格式

对于每组数据，如果小径是幸运的（连续福娃数量恰好等于 ），则输出 ，否则输出 。

样例输入

2
9
111111111
3
110

样例输出

lucky
unlucky

数据范围

• 
• 

样例 解释说明

9 111111111	小径长度为9，所有位置都有福娃，形成了连续9个福娃，恰好等于9，所以是幸运小径。
3 110	小径长度为3，前两个位置有福娃，连续福娃数量为2，不等于9，所以不是幸运小径。

题解

这道题目其实非常直观，我们需要找出字符串中最长的连续 '1' 的数量，然后判断这个数量是否正好等于9。

具体思路如下：

1. 遍历字符串，用一个计数器记录当前连续 '1' 的数量
2. 每当遇到一个 '1'，计数器加1
3. 每当遇到一个 '0'，重置计数器为0
4. 在整个过程中记录最大的连续 '1' 数量
5. 最后判断最大连续数量是否等于9

这个算法的时间复杂度是 O(n)，其中 n 是字符串的长度。我们只需要遍历一次字符串，并在遍历过程中更新最大连续计数即可。空间复杂度是 O(1)，因为我们只使用了常数个变量来记录计数和最大值。

这种方法非常高效，可以轻松处理长度达到 10^5 的字符串。针对本题的特点，我们直接判断最大连续 '1' 的数量是否等于9，一旦发现连续数量超过9，就可以确定答案为 "unlucky"。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取测试数据的组数
T = int(input())
for _ in range(T):
    # 读取小径长度
    n = int(input())
    # 读取表示福娃分布的字符串
    s = input()
    
    # 初始化计数器和最大计数
    cnt = 0
    max_cnt = 0
    
    # 遍历字符串查找最长连续1的数量
    for c in s:
        if c == '1':
            # 如果当前字符是'1'，计数器加1
            cnt += 1
            # 更新最大计数
            max_cnt = max(max_cnt, cnt)
        else:
            # 如果当前字符是'0'，重置计数器
            cnt = 0
    
    # 判断最大连续1的数量是否正好等于9
    if max_cnt == 9:
        print("lucky")
    else:
        print("unlucky")

• Cpp

#include <iostream>
#include <string>
using namespace std;

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        cin >> n;
        
        string s;
        cin >> s;
        
        // 初始化计数器和最大计数
        int cnt = 0, mx = 0;
        
        // 遍历字符串查找最长连续1
        for (char ch : s) {
            if (ch == '1') {
                // 福娃存在，计数器增加
                cnt++;
                // 更新最大值
                mx = max(mx, cnt);
            } else {
                // 福娃不存在，重置计数器
                cnt = 0;
            }
        }
        
        // 判断最大连续数量是否正好为9
        if (mx == 9) {
            cout << "lucky" << "\n";
        } else {
            cout << "unlucky" << "\n";
        }
    }
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取测试组数
        int t = sc.nextInt();
        
        while (t-- > 0) {
            // 读取小径长度
            int n = sc.nextInt();
            
            // 读取福娃分布字符串
            String s = sc.next();
            
            // 初始化计数器和最大值
            int curr = 0;
            int maxLen = 0;
            
            // 遍历字符串
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == '1') {
                    // 如果有福娃，计数器增加
                    curr++;
                    // 更新最大值
                    maxLen = Math.max(maxLen, curr);
                } else {
                    // 如果没有福娃，重置计数器
                    curr = 0;
                }
            }
            
            // 判断最大连续数量是否等于9
            if (maxLen == 9) {
                System.out.println("lucky");
            } else {
                System.out.println("unlucky");
            }
        }
        
        sc.close();
    }
}

02. 糖果店的优惠兑换计划

问题描述

小兰开了一家糖果店，推出了一种特殊的兑换活动。商店有 位顾客，每位顾客最多可以参与一次兑换，总共需要兑换完 个糖果。每张兑换券可以兑换 个糖果，但实际的兑换方式有点特别。

当顾客想兑换 个糖果时，需要的兑换券数量 按照以下公式计算：

也就是说，如果 ，则不需要消耗任何兑换券（）。

小兰的规则是：

• 每位顾客最多只能参与一次兑换活动
• 所有 个糖果必须全部兑换完毕

小兰想知道，要兑换完所有糖果，至少需要多少张兑换券。请你帮忙计算。

输入格式

第一行包含一个正整数 ，表示测试数据组数。

接下来 行，每行包含三个正整数 ，分别表示顾客数量、需要兑换的糖果总数以及每张兑换券可兑换的糖果数量。

• 
• 
• 

输出格式

输出 行，每行一个整数，表示最少需要的兑换券数量。

样例输入

2
3 300 100
2 100 160

样例输出

2
0

数据范围

• 
• 
• 
• 

样例 解释说明

3 300 100	有3位顾客，需要兑换300个糖果，每张券兑换100个。 当k=100时，可以免费兑换的最大糖果数为49个。 3位顾客共可免费兑换3×49=147个糖果。 剩余300-147=153个糖果需要使用兑换券。 使用2张兑换券可以再兑换2×100=200个糖果，足够覆盖剩余的153个。 因此最少需要2张兑换券。
2 100 160	有2位顾客，需要兑换100个糖果，每张券兑换160个。 当k=160时，可以免费兑换的最大糖果数为79个。 2位顾客共可免费兑换2×79=158个糖果。 这已经超过了需要兑换的100个糖果，因此不需要使用任何兑换券。 答案为0。

题解

这道题乍看有点复杂，但分析后会发现解题思路其实很清晰。

首先，我们需要理解兑换券的使用规则。通过分析给定的公式，我们可以得知，当兑换的糖果数量小于 k/2 时，不需要使用任何兑换券。这就意味着每位顾客都有一个"免费额度"，可以不用兑换券就能兑换一定数量的糖果。

具体来说：

• 当 k 为偶数时，免费兑换的最大糖果数量是 k/2 - 1
• 当 k 为奇数时，免费兑换的最大糖果数量是 (k-1)/2

我们的策略是先利用所有顾客的免费额度，看能兑换多少糖果。如果这些免费额度总和已经超过了需要兑换的糖果总数 m，那么不需要使用任何兑换券。否则，我们需要计算还需要多少张兑换券来兑换剩余的糖果。

注意，每使用一张兑换券，就可以多兑换 k 个糖果。所以，剩余糖果数除以 k 并向上取整，就是我们需要的兑换券数量。

这个解法的时间复杂度是 O(T)，其中 T 是测试数据的组数。每组数据我们只需要进行几个简单的计算即可。

空间复杂度是 O(1)，因为我们只使用了常数个变量来存储中间结果。

对于给定的数据范围，我们需要使用长整型（long long）来处理可能的大数，特别是对于 n 和 m 这两个可能很大的输入。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取测试用例数量
T = int(input())

for _ in range(T):
    # 读取n, m, k
    n, m, k = map(int, input().split())
    
    # 计算每位顾客免费兑换的最大糖果数量
    if k % 2 == 0:
        # k为偶数
        free = k // 2 - 1
    else:
        # k为奇数
        free = (k - 1) // 2
    
    # 计算所有顾客总共可以免费兑换的糖果数量
    total_free = n * free
    
    if total_free >= m:
        # 免费额度足够，不需要兑换券
        print(0)
    else:
        # 计算还需要多少兑换券
        remain = m - total_free
        # 每张兑换券可以兑换k个糖果，向上取整
        coupons = (remain + k - 1) // k
        print(coupons)

• Cpp

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        long long n, m, k;
        cin >> n >> m >> k;
        
        // 计算每位顾客的免费额度
        long long free;
        if (k % 2 == 0) {
            // k为偶数
            free = k / 2 - 1;
        } else {
            // k为奇数
            free = (k - 1) / 2;
        }
        
        // 计算总免费额度
        long long tot = n * free;
        
        if (tot >= m) {
            // 免费额度足够
            cout << 0 << "\n";
        } else {
            // 需要使用兑换券
            long long need = m - tot;
            // 向上取整计算所需兑换券数量
            long long ans = (need + k - 1) / k;
            cout << ans << "\n";
        }
    }
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取测试用例数量
        int t = sc.nextInt();
        
        while (t-- > 0) {
            // 读取顾客数量n、糖果总数m和每张券兑换糖果数k
            long n = sc.nextLong();
            long m = sc.nextLong();
            long k = sc.nextLong();
            
            // 计算每位顾客的免费额度
            long fAmt;
            if (k % 2 == 0) {
                // k为偶数
                fAmt = k / 2 - 1;
            } else {
                // k为奇数
                fAmt = (k - 1) / 2;
            }
            
            // 计算总免费额度
            long total = n * fAmt;
            
            if (total >= m) {
                // 如果免费额度足够
                System.out.println(0);
            } else {
                // 计算需要的额外糖果数量
                long extra = m - total;
                // 向上取整计算所需兑换券
                long result = (extra + k - 1) / k;
                System.out.println(result);
            }
        }
        
        sc.close();
    }
}

03. 数字重排最大化问题

问题描述

小基是一位专业的数字设计师。她手中有两个数字序列 和 ，都由正整数组成。小基可以对序列 进行任意次操作，每次操作可以交换 中任意两个数字的位置。

小基的目标是让序列 组成的数字尽可能大，但必须严格小于序列 组成的数字。

请你帮助小基计算，在可以进行任意次交换操作后，符合条件的 所能组成的最大数字是多少。如果不存在符合条件的方案，请输出 。

输入格式

第一行包含一个正整数 ，表示测试数据的组数。

对于每组测试数据，分别有三行：

第一行包含两个正整数 和 ，分别表示序列 和 的长度。

第二行包含 个正整数，表示序列 的元素。

第三行包含 个正整数，表示序列 的元素。

输出格式

对于每组数据，输出一个整数，表示序列 经过任意次交换操作后，所能组成的最大且小于 的数字。

如果不存在这样的数字，则输出 。

样例输入

3
5 5
12345
45678
5 5
65479
54231
5 5
42315
12345

样例输出

45321
49765
-1

数据范围

• 
• 
• 序列中的每个元素都是正整数（1-9）

样例 解释说明

5 5 12345 45678	序列s1=[1,2,3,4,5]，序列s2=[4,5,6,7,8] 将s1重排为[4,5,3,2,1]，组成的数字45321 这是小于s2组成的数字45678的最大可能值
5 5 65479 54231	序列s1=[6,5,4,7,9]，序列s2=[5,4,2,3,1] 将s1重排为[4,9,7,6,5]，组成的数字49765 这是小于s2组成的数字54231的最大可能值
5 5 42315 12345	序列s1=[4,2,3,1,5]，序列s2=[1,2,3,4,5] 无论如何重排s1，都无法使其组成的数字小于s2 因此输出-1

题解

这道题需要我们