笔试时间：2024年09月29日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

有n个插在数轴上的木板，其中第i块木板高度为ai，相邻木板之间的宽度为1，木板本身的宽度忽略不计。

现在要使用这n个木板来接雨水，想知道如他可以提前调整这些木板的排列顺序，那么最多可以接多少雨水？

输入描述

第一行输入一个整数 n（2 <= n <= 2 * 10^5）代表数组中的元素数量。

第二行输入n个整数a1,a2,...an表示每块木板的高度。

输出描述

在一行上输出一个整数，代表在任意排列所有木板后，可以接到雨水的最大量。

样例输入

4

1 3 4 5

样例输出

12

参考题解

模拟。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>

using namespace std;

long long maxRainwater(int n, vector<long long>& heights) {
    // 找到最高和第二高的木板
    long long max1 = LLONG_MIN, max2 = LLONG_MIN;

    for (long long height : heights) {
        if (height > max1) {
            max2 = max1;
            max1 = height;
        } else if (height > max2) {
            max2 = height;
        }
    }

    // 计算可以接的雨水总量
    return max2 * (n - 1);
}

int main() {
    int n;
    cin >> n;
    vector<long long> heights(n); // 使用 long long 类型

    for (int i = 0; i < n; i++) {
        cin >> heights[i];
    }

    // 输出结果
    cout << maxRainwater(n, heights) << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class MaxRainwater {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        long[] heights = new long[n];
        for (int i = 0; i < n; i++) {
            heights[i] = scanner.nextLong(); // 使用 long 类型
        }

        // 计算接水量
        System.out.println(maxRainwater(n, heights));
    }

    public static long maxRainwater(int n, long[] heights) {
        // 找到最高和第二高的木板
        long max1 = Long.MIN_VALUE;
        long max2 = Long.MIN_VALUE;

        for (long height : heights) {
            if (height > max1) {
                max2 = max1;
                max1 = height;
            } else if (height > max2) {
                max2 = height;
            }
        }

        // 计算可以接的雨水总量
        return max2 * (n - 1);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def max_rainwater(n, heights):
    # 找到最高和第二高的木板
    max1 = max(heights)
    heights.remove(max1)  # 移除最高木板后再找第二高
    max2 = max(heights)

    # 计算可以接的雨水总量
    rainwater = max2 * (n - 1)
    return rainwater

# 读取输入
n = int(input())
heights = list(map(int, input().split()))

# 输出结果
print(max_rainwater(n, heights))

第二题

题目

小苯有一个长度为n的数组a1, a2, a3...an，和一个初始为空的双端队列q。在这里，双端队列是一种数据结构，其两端都可以放入元素，你可以参考样例解释获得更形象的说明。他想要将数组中的元素从左到右依次取出、放入q中。是否存在一种放入方式，使得全部数字放入后，q中的元素从左到右单调不降。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数T(1<= T <= 10 ^4 )代表数据组数，每组测试数据描述如下:

第一行输入一个正整数n代表数组中的元素数量。

第二行输入n个整数a1, a2, ...ai，代表数组中的元素。

输出描述

对于每一组测试数据，如果存在这样的放入方式，在一行上输出YES，否则，直接输出NO。

样例输入

3

4

2 3 1 4

3

1 1 1

3 

1 3 2

样例输出

YES

YES

NO

参考题解

贪心的根据当前元素与队列两端元素的大小关系，选择小的来插入，以确保队列单调不降。如果无法满足条件，则返回 "NO"。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <deque>
#include <vector>
#include <string>

using namespace std;

string canFormNonDecreasingQueue(int n, vector<int>& a) {
    deque<int> q;
    for (int num : a) {
        if (q.empty()) { // 如果队列为空，直接放入
            q.push_back(num);
        } else {
            // 比较并决定放入左端还是右端
            if (num >= q.back()) { // 如果当前元素大于等于右端元素，放右边
                q.push_back(num);
            } else if (num <= q.front()) { // 如果当前元素小于等于左端元素，放左边
                q.push_front(num);
            } else { // 如果两者都不符合，返回 NO
                return "NO";
            }
        }
    }
    return "YES";
}

int main() {
    int T;
    cin >> T; // 读取测试案例数量
    string results;

    for (int i = 0; i < T; i++) {
        int n;
        cin >> n; // 读取每个测试案例的元素数量
        vector<int> a(n);
        for (int j = 0; j < n; j++) {
            cin >> a[j]; // 读取元素
        }
        results += canFormNonDecreasingQueue(n, a) + "\n"; // 将结果加入结果字符串
    }
    cout << results; // 输出所有结果
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main{
    public static String canFormNonDecreasingQueue(int n, int[] a) {
        Deque<Integer> q = new ArrayDeque<>();
        for (int num : a) {
            if (q.isEmpty()) { // 如果队列为空，直接放入
                q.add(num);
            } else {
                // 比较并决定放入左端还是右端
                if (num >= q.peekLast()) { // 如果当前元素大于等于右端元素，放右边
                    q.add(num);
                } else if (num <= q.peekFirst()) { // 如果当前元素小于等于左端元素，放左边
                    q.addFirst(num);
                } else { // 如果两者都不符合，返回 NO
                    return "NO";
                }
            }
        }
        return "YES";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 读取测试案例数量
        StringBuilder results = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt(); // 读取每个测试案例的元素数量
            int[] a = new int[n];
            for (int j = 0; j < n; j++) {
                a[j] = scanner.nextInt(); // 读取元素
            }
            results.append(canFormNonDecreasingQueue(n, a)).append("\n");
        }
        System.out.print(results); // 输出所有结果
        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

from collections import deque

def can_form_non_decreasing_queue(n, a):
    q = deque()
    for num in a:
        if not q:  # 如果队列为空，直接放入
            q.append(num)
        else:
            # 比较并决定放入左端还是右端
            if num >= q[-1]:  # 如果当前元素大于等于右端元素，放右边
                q.append(num)
            elif num <=