✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

小米

题目一：魔法水晶阵列能量统计

1️⃣：枚举中间元素，使用树状数组统计左侧较小元素和右侧较大元素数量

2️⃣：离散化处理值域，利用数学公式计算严格递增三元组个数

难度：中等

这道题目的核心在于理解如何优化三元组统计问题。通过观察发现可以枚举中间元素，然后利用树状数组快速计算左右两侧满足条件的元素个数。离散化技巧用于处理大值域问题，最终实现 O(n log n) 的高效解法。

题目二：智能仓储机器人调度系统

1️⃣：将问题建模为双端队列，理解两个出口的工作机制

2️⃣：使用贪心策略模拟过程，优先从尾部取出以最大化目标

难度：中等

这道题目结合了数据结构和贪心思想，关键在于理解双端队列的特性以及两个出口的限制条件。通过模拟整个调度过程，并采用贪心策略来最大化从指定出口出库的货物数量，体现了算法设计中建模和优化的重要性。

01. 魔法水晶阵列能量统计

问题描述

小兰是一位魔法研究者，她在古老的魔法图书馆中发现了一个神秘的魔法水晶阵列。这个阵列由 颗魔法水晶组成，每颗水晶都蕴含着不同强度的魔法能量。

经过深入研究，小兰发现了水晶阵列的能量释放规律：当存在三颗水晶满足以下条件时，它们可以形成一个稳定的魔法三角阵，释放出强大的能量波动。

设这三颗水晶的位置分别为 、、（），它们的魔法能量值分别为 、、，则需要满足：

• （能量值严格递增）

小兰想要知道，在这个魔法水晶阵列中，总共能够形成多少个这样的魔法三角阵。

输入格式

第一行包含一个正整数 （），表示魔法水晶的数量。

第二行包含 个正整数 （），表示每颗魔法水晶的能量值。

输出格式

输出一个整数，表示可以形成的魔法三角阵的总数。

样例输入

4
22 11 66 99

样例输出

2

样例	解释说明
样例1	在序列 [22, 11, 66, 99] 中，可以形成的魔法三角阵有：(1,3,4) 对应 22<66<99，以及 (2,3,4) 对应 11<66<99，共2个

数据范围

• 
• 

题解

这道题本质上是要统计所有满足 且 的三元组个数。

最直观的想法是三重循环枚举所有可能的 组合，但时间复杂度为 ，对于 的数据会超时。

观察发现，可以枚举中间元素 ，然后计算：

• leftSmaller[j]：在位置 左侧且小于 的元素个数
• rightGreater[j]：在位置 右侧且大于 的元素个数

那么以 为中心能组成的三元组数量就是 leftSmaller[j] × rightGreater[j]，答案就是所有 对应结果的总和。

为了快速计算这两个值，可以使用树状数组（Binary Indexed Tree）来维护区间内元素的个数。由于 的值域较大，需要先进行离散化处理。

具体算法流程：

1. 对输入序列进行离散化处理
2. 维护两个树状数组：左侧树状数组和右侧树状数组
3. 初始时将所有元素都加入右侧树状数组
4. 从左到右遍历每个位置 ：
   • 从右侧树状数组中移除
   • 查询左侧小于 的元素个数
   • 查询右侧大于 的元素个数
   • 将两者相乘加入答案
   • 将 加入左侧树状数组

时间复杂度为 ，可以通过所有测试用例。

参考代码

Python

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, idx, val):
        # 在位置idx加上val
        while idx <= self.n:
            self.tree[idx] += val
            idx += idx & (-idx)
    
    def query(self, idx):
        # 查询前缀和[1..idx]
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & (-idx)
        return res
    
    def range_query(self, l, r):
        # 查询区间[l,r]的和
        if l > r:
            return 0
        return self.query(r) - self.query(l - 1)

n = int(input())
a = list(map(int, input().split()))

# 离散化处理
vals = sorted(set(a))
pos_map = {v: i + 1 for i, v in enumerate(vals)}
m = len(vals)

# 将原数组映射为离散化后的值
disc_a = [pos_map[x] for x in a]

bit_l = BIT(m)  # 左侧树状数组
bit_r = BIT(m)  # 右侧树状数组

# 初始时所有元素都在右侧
for x in disc_a:
    bit_r.update(x, 1)

ans = 0
for j in range(n):
    cur = disc_a[j]
    
    # 从右侧移除当前元素
    bit_r.update(cur, -1)
    
    # 计算左侧小于当前元素的个数
    left_cnt = bit_l.query(cur - 1)
    
    # 计算右侧大于当前元素的个数  
    right_cnt = bit_r.range_query(cur + 1, m)
    
    # 累加到答案
    ans += left_cnt * right_cnt
    
    # 将当前元素加入左侧
    bit_l.update(cur, 1)

print(ans)

C++

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

struct BIT {
    int n;
    vector<long long> tr;
    
    BIT(int _n = 0) { init(_n); }
    
    void init(int _n) {
        n = _n;
        tr.assign(n + 1, 0);
    }
    
    void add(int idx, long long val = 1) {
        // 在位置idx加上val
        for (; idx <= n; idx += idx & -idx) {
            tr[idx] += val;
        }
    }
    
    long long sum(int idx) const {
        // 查询前缀和[1..idx]
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx) {
            res += tr[idx];
        }
        return res;
    }
    
    long long range_sum(int l, int r) const {
        // 查询区间[l,r]的和
        return sum(r) - sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    
    // 离散化处理
    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    
    for (int &x : a) {
        x = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
    }
    
    int m = vals.size();
    BIT bit_l(m), bit_r(m);
    
    // 初始时所有元素都在右侧
    for (int x : a) {
        bit_r.add(x, 1);
    }
    
    long long ans = 0;
    for (int j = 0; j < n; j++) {
        int cur = a[j];
        
        // 从右侧移除当前元素
        bit_r.add(cur, -1);
        
        // 计算左侧小于当前元素的个数
        long long left_cnt = bit_l.sum(cur - 1);
        
        // 计算右侧大于当前元素的个数
        long long right_cnt = bit_r.range_sum(cur + 1, m);
        
        // 累加到答案
        ans += left_cnt * right_cnt;
        
        // 将当前元素加入左侧
        bit_l.add(cur, 1);
    }
    
    cout << ans << "\n";
    return 0;
}

Java

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

class Main {
    static class BIT {
        private int n;
        private long[] tree;