✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

🌸 目前本专栏已经上线140+套真题改编解析，后续会持续更新的

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

题目一：小兰的数字堡垒防御系统

1️⃣：分析攻击模式，将总攻击次数分解为左端攻击和右端攻击

2️⃣：使用双指针技术从两端同时消耗攻击次数，统计被击毁节点数

难度：中等

这道题目的关键在于理解交替攻击的模式，并发现可以将其转化为双端同时攻击的问题。通过数学分析，可以避免直接模拟每次攻击，实现 O(n) 的高效解法。

题目二：小基的智能交通系统优化

1️⃣：二分答案，枚举可能的容错阈值

2️⃣：动态规划求解最长可保留子序列，利用跨距条件进行状态转移

3️⃣：基于保留子序列长度判断所需修改次数是否满足约束

难度：中等

这道题目结合了二分搜索和动态规划算法，关键洞察是将问题转化为寻找最长的满足跨距条件的保留子序列。通过 DP 优化，可以在 O(n²log V) 时间内找到最优解。

01. 小兰的数字堡垒防御系统

问题描述

小兰负责管理一个数字堡垒的防御系统。该系统由 个防御节点组成，编号从 到 ，按顺序排列在防御链上。第 个防御节点的能量值为 。

当外敌入侵时，攻击程序会按照特定的模式对防御系统发动 次攻击。攻击顺序如下：首先攻击防御链的第一个节点，然后攻击最后一个节点，接着再攻击第一个节点，依此类推。

每次攻击会使目标节点的能量值减少 。当某个节点的能量值降至 时，该节点就会失效，不再是攻击目标（因此该节点不再被视为第一个或最后一个节点，攻击程序只会攻击仍然有效的节点）。如果所有节点都失效了，攻击程序就会停止运行。

例如，如果 ，且 ，将会发生以下情况：

• 攻击程序攻击第一个节点，其能量值变为 ，现在 ；

• 攻击程序攻击最后一个节点，现在 ；

• 攻击程序攻击第一个节点，现在 ；

• 攻击程序攻击最后一个节点，现在 ；

• 攻击程序攻击第一个节点，其能量值变为 ，现在 。

请问攻击结束后有多少个防御节点失效了？

输入格式

输入包括多组测试数据。

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

对于每个测试用例：

第一行包含两个整数 和 ，表示防御节点的数量以及攻击程序攻击的次数。

第二行包含 个整数 ，表示各个防御节点的能量值。

输出格式

对于每个测试用例，在单独的一行中输出被攻击程序击毁的防御节点数量。

样例输入

6
4 5
1 2 4 3
4 6
1 2 4 3
5 20
2 7 1 8 2
2 2
3 2
2 15
1 5
2 7
5 2

样例输出

2
3
5
0
2
2

数据范围

题解

这道题的关键在于理解攻击模式：攻击程序交替攻击防御链的两端。可以把这个过程看作是从两端同时消耗能量值。

首先分析攻击模式。假设总共有 次攻击，那么：

• 奇数次攻击（第1、3、5...次）攻击左端，总共 次
• 偶数次攻击（第2、4、6...次）攻击右端，总共 次

这样就把问题转化为：用 点伤害从左端开始依次攻击，用 点伤害从右端开始依次攻击。

具体算法步骤：

1. 计算左端攻击次数 和右端攻击次数
2. 使用双指针 和 分别指向当前的左端和右端
3. 从左端开始消耗 点伤害，每当能完全击毁一个节点时，移动左指针并增加击毁计数
4. 从右端开始消耗 点伤害，类似处理
5. 最后检查是否还有中间节点，如果左右指针相遇且剩余伤害足够击毁该节点，则也计入

这种方法的时间复杂度是 ，远小于直接模拟 次攻击的复杂度。

参考代码

• Python

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

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    # 计算左端和右端的攻击次数
    left_att = (k + 1) // 2  # 奇数次攻击
    right_att = k // 2       # 偶数次攻击
    
    l, r = 0, n - 1  # 双指针
    destroyed = 0    # 被击毁的节点数
    
    # 从左端消耗攻击次数
    while l <= r and left_att >= a[l]:
        left_att -= a[l]
        destroyed += 1
        l += 1
    
    # 从右端消耗攻击次数
    while r >= l and right_att >= a[r]:
        right_att -= a[r]
        destroyed += 1
        r -= 1
    
    # 检查中间是否还有一个节点
    if l == r:
        if left_att + right_att >= a[l]:
            destroyed += 1
    
    return destroyed

t = int(input())
for _ in range(t):
    print(solve())

• Cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        ll k;
        cin >> n >> k;
        
        vector<ll> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 计算左右攻击次数
        ll left_dmg = (k + 1) / 2;  // 奇数次攻击
        ll right_dmg = k / 2;       // 偶数次攻击
        
        int l = 0, r = n - 1;
        ll killed = 0;
        
        // 从左端开始攻击
        while (l <= r && left_dmg >= a[l]) {
            left_dmg -= a[l];
            killed++;
            l++;
        }
        
        // 从右端开始攻击
        while (r >= l && right_dmg >= a[r]) {
            right_dmg -= a[r];
            killed++;
            r--;
        }
        
        // 检查中间节点
        if (l == r && left_dmg + right_dmg >= a[l]) {
            killed++;
        }
        
        cout << killed << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            String[] nk = br.readLine().split(" ");
            int n = Integer.parseInt(nk[0]);
            long k = Long.parseLong(nk[1]);
            
            String[] aStr = br.readLine().split(" ");
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(aStr[i]);
            }
            
            // 计算左右攻击伤害
            long leftDamage = (k + 1) / 2;  // 奇数次攻击
            long right