笔试时间：2024年03月23日

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

第一题

题目：移山

天帝被愚公的诚心感动，命令手下的仙人帮助移山。然而仙人的法术也是有局限性的，山势连绵起伏，法术并不能直接把山移走。每次施法，可以把一段连续区域的山头移走相同高度。现在愚公想知道什么时候会有至少一个山头高度小于等于0。给出一个长度为n的数组a1,……,an，和m表示山头的高度和可以施法的次数，每次施法还会给出左右端点L,R,和高度h，表示将aL…,aR,依次减去h。问在哪次操作之后存在一个ai≤0?(数据保证这样的时刻存在。)

输入描述

第一行两个数n和m，表示山头数量和施法次数。

第二行n个数，分别表示第a1,…,an，即第一个山头到第n个山头的高度。

接下来m行，每行三个数L,R,h，表示一次施法的具体参数。

1≤n,m≤10的5次方,1≤h,ai≤10的9次方,1≤L≤R≤n，均为整数。

输出描述

输出一个整数，表示答案。数据保证答案存在。

样例输入

5 4

6 5 3 4 6

1 3 2

4 4 2

3 5 1

样例输出

3

说明

第一次操作之后山头变成4 3 1 4 6

第二次操作之后山头变成4 3 1 2 6

第三次操作之后山头变成4 3 0 1 5

其中第三个山头高度小于等于了0，可见，在第三次施法之后有一个山头的高度变成了0

参考题解

看样例，选择直接模拟。

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

#include <iostream>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int L ,R ,H;
int a[N];

bool check()
{
    for(int i = L ; i <= R ; ++i)
    {
        a[i] -= H;
        if(a[i] <= 0) return true;
    }
    return false;
}

int main()
{
    int n ,m;
    cin>>n>>m;
    for(int i = 0 ; i < n ; ++i)
    {
        scanf("%d" , &a[i]);
    }
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d%d" , &L , &R , &H);
        if(check())
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

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

import java.util.Scanner;

public class Main {
    static final int N = 100010;
    static int L, R, H;
    static int[] a = new int[N];

    static boolean check() {
        for (int i = L; i <= R; ++i) {
            a[i] -= H;
            if (a[i] <= 0) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i <= m; ++i) {
            L = scanner.nextInt();
            R = scanner.nextInt();
            H = scanner.nextInt();
            if (check()) {
                System.out.println(i);
                return;
            }
        }
    }
}

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

N = 100010
a = [0] * N

def check():
    global a, L, R, H
    for i in range(L, R+1):
        a[i] -= H
        if a[i] <= 0:
            return True
    return False

if __name__ == "__main__":
    n, m = map(int, input().split())
    a[:n] = map(int, input().split())
    for i in ran