💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍥 本次难度不大，是需要争取AK的一场哦～

1️⃣ 思维题，找到次大值

2️⃣ 模拟题，每次判断当前数是否大于/小于极值

3️⃣ 小学数学题，比较简单，考查最大公约数，最小公倍数的求法

4️⃣ 单调栈模版题，需要找到 >= 当前数的第一个位置在哪里

☔️01.雨水收集系统 评测链接🔗

问题描述

LYA 是一位环保工程师，她正在设计一个创新的雨水收集系统。这个系统由 个垂直的收集板组成，每个收集板都有不同的高度。这些收集板将被安装在一条直线上，相邻板之间的距离恰好为 1 单位。收集板的宽度可以忽略不计。

LYA 想要知道，如果她可以任意调整这些收集板的排列顺序，那么这个系统最多能收集多少单位的雨水。

输入格式

第一行输入一个整数 （），表示收集板的数量。

第二行输入 个整数 （），表示每个收集板的高度。

输出格式

输出一个整数，表示在最优排列下，系统能够收集的最大雨水量。

样例输入

4
1 3 4 5

样例输出

12

数据范围

题解

思维

关键洞察：为了最大化收集的雨水量，我们应该让次高的板成为"瓶颈"。也就是说，除了最高的板，其他所有的板都应该贡献它们的全部高度。

最优的排列方式是：将最高的板放在一端，次高的板放在另一端，其他板放在中间（顺序不重要）。

• 这样，除了最高的板，其他每个板都会贡献自己的全部高度来收集雨水。

• 计算公式：总雨水量 = (n - 1) * 次高板的高度，这是因为有 n-1 个间隔，每个间隔都可以装满到次高板的高度。

• Python

# 读取输入
n = int(input())  # 读取收集板的数量
heights = list(map(int, input().split()))  # 读取每个收集板的高度

# 对高度进行排序
heights.sort()

# 计算最大雨水量
# 次高的板高度 * (收集板数量 - 1)
max_water = heights[-2] * (n - 1)

# 输出结果
print(max_water)

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();  // 读取收集板的数量
        int[] heights = new int[n];  // 创建数组存储收集板高度
        for (int i = 0; i < n; i++) {
            heights[i] = scanner.nextInt();  // 读取每个收集板的高度
        }
        
        // 对高度进行排序
        Arrays.sort(heights);
        
        // 计算最大雨水量
        // 次高的板高度 * (收集板数量 - 1)
        long maxWater = (long) heights[n - 2] * (n - 1);
        
        // 输出结果
        System.out.println(maxWater);
        
        scanner.close();
    }
}

• Cpp

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;  // 读取收集板的数量
    
    vector<int> heights(n);
    for (int i = 0; i < n; i++) {
        cin >> heights[i];  // 读取每个收集板的高度
    }
    
    // 对高度进行排序
    sort(heights.begin(), heights.end());
    
    // 计算最大雨水量
    // 次高的板高度 * (收集板数量 - 1)
    long long maxWater = 1LL * heights[n - 2] * (n - 1);
    
    // 输出结果
    cout << maxWater << "\n";
    
    return 0;
}

✨ 02.LYA的魔法队列 评测链接🔗

问题描述

LYA是一位魔法学院的学生，她最近在学习一种名为"魔法队列"的咒语。这个咒语可以创造一个特殊的双端队列，可以从两端添加元素。LYA有一串魔法符文，她想知道是否能通过某种方式将这些符文放入魔法队列中，使得最终队列中的符文能量从左到右呈非递减排列。

LYA需要你的帮助来判断这是否可能。如果可能，请告诉她"YES"，否则告诉她"NO"。

输入格式

第一行输入一个整数 （），表示测试用例的数量。

对于每个测试用例：

• 第一行输入一个正整数 （），表示魔法符文的数量。
• 第二行输入 个整数 （），表示每个魔法符文的能量值。

保证所有测试用例中 的总和不超过 。

输出格式

对于每个测试用例，如果存在一种放置方法使得最终队列中的符文能量从左到右非递减，输出一行 "YES"，否则输出一行 "NO"。

样例输入

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

样例输出

YES
YES
NO

数据范围

• 
• 
• 
• 所有测试用例中 的总和不超过

题解

模拟

首先，需要明白，双端队列允许从两端添加元素。这意味对于每个新的符文，有两个选择：将它放在队列的左端或右端。

解决这个问题的关键思路是：

1. 维护当前队列中的最小值和最大值。
2. 对于每个新的符文，判断它是否可以放入队列而不破坏非递减的性质。

• 如果新符文的能量值小于或等于当前最小值，可以将它放在队列的左端。
• 如果新符文的能量值大于或等于当前最大值，可以将它放在队列的右端。
• 如果新符文的能量值既大于最小值又小于最大值，那么无论放在哪里都会破坏非递减的性质。

参考代码

• Python

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

for _ in range(t):
    # 读取符文数量
    n = int(input())
    # 读取符文能量值
    a = list(map(int, input().split()))
    
    # 初始化最小值和最大值
    min_val = max_val = a[0]
    possible = True
    
    # 遍历剩余的符文
    for i in range(1, n):
        if a[i] <= min_val:
            # 可以放在左端
            min_val = a[i]
        elif a[i] >= max_val:
            # 可以放在右端
            max_val = a[i]
        else:
            # 无法放置
            possible = False
            break
    
    # 输出结果
    print("YES" if possible else "NO")

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取测试用例数量
        int t = scanner.nextInt();
        
        while (t-- > 0) {
            // 读取符文数量
            int n = scanner.nextInt();
            int[] a = new int[n];
            
            // 读取符文能量值
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            
            // 初始化最小值和最大值
            int minVal = a[0], maxVal = a[0];
            boolean possible = true;
            
            // 遍历剩余的符文
            for (int i = 1; i < n; i++) {
                if (a[i] <= minVal) {
                    // 可以放在左端
                    minVal = a[i];
                } else if (a[i] >= maxVal) {
                    // 可以放在右端
                    maxVal = a[i];
                } else {
                    // 无法放置
                    possible = false;
                    break;
                }
            }
            
            // 输出结果
            System.out.println(possible ? "YES" : "NO");
        }
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;  // 读取测试用例数量
    
    while (t--) {
        int n;
        cin >> n;  // 读取符文数量
        vector<int> a(n);
        
        // 读取符文能量值
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 初始化最小值和最大值
        int min_val = a[0], max_val = a[0];