✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魔法水晶阵列能量优化

1️⃣：理解逆序对的变化规律，分析区间操作对逆序对的影响

2️⃣：选择后缀区间避免产生新的逆序对，只最大化消除的逆序对

3️⃣：使用线性扫描维护前缀后缀统计，计算每个位置的收益

难度：中等

这道题目的关键在于理解对区间进行 +1 操作时逆序对数量的变化规律。通过数学分析发现，选择后缀区间是最优策略，可以避免产生新的逆序对。使用双指针和计数数组，可以在 O(n) 时间内求解。

题目二：艺术品评审最佳区间选择

1️⃣：理解题目要求，需要最大化去除最大最小值后的平均值

2️⃣：使用滑动窗口遍历所有长度为 m 的连续子数组

3️⃣：利用 multiset 或 TreeMap 维护窗口内元素的有序性

难度：中等

这道题目结合了滑动窗口和数据结构维护。关键在于发现只需最大化分子部分，然后使用合适的数据结构来快速维护窗口内的最大值和最小值。通过 multiset 可以实现 O(n log m) 的高效解法。

01. 魔法水晶阵列能量优化

问题描述

小基 正在研究一个古老的魔法水晶阵列。这个阵列由 个水晶组成，每个水晶都有一个能量等级 。由于水晶之间的相互作用，当能量等级较高的水晶位于能量等级较低的水晶前面时，会产生能量冲突，造成魔法不稳定。

具体来说，如果存在位置 且 ，那么这一对水晶 会产生一次能量冲突。小基 需要计算整个阵列中能量冲突的总数。

为了优化阵列的稳定性，小基 可以对阵列进行至多一次魔法增强操作：选择一个连续的区间 （其中 ），将区间内所有水晶的能量等级同时提升 。

小基 想知道，通过最优的魔法增强操作，最多能够减少多少次能量冲突？

输入格式

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

对于每组测试数据：

• 第一行包含一个正整数 ，表示水晶阵列的长度。
• 第二行包含 个正整数 ，表示每个水晶的能量等级。

输出格式

对于每组测试数据，输出一个整数，表示通过最优的魔法增强操作能够减少的最大能量冲突数。

样例输入

3
5
4 2 3 1 5
5
1 2 3 4 5
3
2 1 1

样例输出

2
0
2

数据范围

样例	解释说明
样例1	选择区间 ，变化后的序列为 ，原来有5个冲突，现在有3个冲突，减少了2个
样例2	序列已经有序，无论选择哪个区间都无法减少冲突数
样例3	选择区间 ，变化后的序列为 ，原来有2个冲突，现在没有冲突，减少了2个

题解

这道题要求通过一次区间加1操作来最大化减少的逆序对数量。

核心思路

观察区间操作对逆序对的影响：当选择区间 进行加1操作时，只有跨区间边界的元素对会改变逆序关系。

1. 消除逆序对：如果 且 ，操作后 变为 ，逆序对被消除
2. 新增逆序对：如果 且 ，操作后 变为 ，产生新逆序对

算法策略

从右向左枚举区间起点，动态维护两个频次数组：

• suffix_count[x]：右侧未进入区间的值为 的元素个数
• prefix_incr[x]：已进入区间且变为值 的元素个数（原值为 ）

对于当前位置 ，元素 进入区间后：

• 消除的逆序对：suffix_count[a[i] + 1]（右侧值为 的元素与当前 形成的逆序对）
• 新增的逆序对：prefix_incr[a[i]]（左侧已加1变为 的元素与右侧值为 的元素形成的逆序对）

时间复杂度： 空间复杂度：

参考代码

• Python

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

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        
        max_val = n + 3
        suffix_cnt = [0] * max_val   # 右侧还未加入区间的值的频次
        prefix_add = [0] * max_val   # 左侧已加入区间变成某值的频次
        
        # 初始化：所有值都在右侧
        for val in arr:
            suffix_cnt[val] += 1
        
        gain = 0
        max_gain = 0
        
        # 从右向左枚举区间左端点
        for pos in range(n - 1, -1, -1):
            val = arr[pos]
            suffix_cnt[val] -= 1
            gain += suffix_cnt[val + 1]  # 消除的逆序对数
            gain -= prefix_add[val]      # 产生的逆序对数
            prefix_add[val + 1] += 1     # 当前值加1后进入左侧统计
            max_gain = max(max_gain, gain)
        
        print(max_gain)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        int n;
        cin >> n;
        vector<int> seq(n);
        for (int i = 0; i < n; i++) {
            cin >> seq[i];
        }

        int range = n + 3;
        vector<long long> right_freq(range, 0), left_incr(range, 0);
        
        // 统计初始频次（所有元素都在右侧）
        for (int val : seq) {
            right_freq[val]++;
        }

        long long delta = 0, answer = 0;
        
        // 从右向左扫描
        for (int idx = n - 1; idx >= 0; idx--) {
            int elem = seq[idx];
            right_freq[elem]--;
            delta += right_freq[elem + 1];  // 减少的逆序对
            delta -= left_incr[elem];       // 增加的逆序对
            left_incr[elem + 1]++;          // 元素进入区间后数值+1
            answer = max(answer, delta);
        }
        
        cout << answer << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int testCount = Integer.parseInt(reader.readLine());
        
        while (testCount-- > 0) {
            int size = Integer.parseInt(reader.readLine());
            int[] nums = new int[size];
            
            StringTokenizer tokens = new StringTokenizer(reader.readLine());
            for (int i = 0; i < size; i++) {
                nums[i] = Integer.parseInt(tokens.nextToken());
            }
            
            int maxRange = size + 3;