首页 > 试题广场 >

移山

[编程题]移山

热度指数：1171 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行两个数  和 ，表示山头数量和施法次数。
第二行个数，分别表示 ，即第一个山头到第 个山头的高度。
接下来m行，每行三个数，表示一次施法的具体参数。

，均为整数

输出描述:

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

示例1

输入

输出

说明

第一次操作之后山头变成4 3 1 4 6
第二次操作之后山头变成4 3 1 2 6
第三次操作之后山头变成4 3 0 1 5
其中第三个山头高度小于等于了0，可见，在第三次施法之后有一个山头的高度变成了0

算法知识视频讲解

nightcherry

import java.util.Arrays;
import java.util.Scanner;
import java.lang.Math;

public class Main {
    static class SegmentTree {
        int n;
        int[] tree;
        int[] lazy;  // 添加懒惰标记

        public SegmentTree(int[] mountains) {
            n = mountains.length;
            tree = new int[n * 4];
            lazy = new int[n * 4];
            build(0, 0, n - 1, mountains);
        }

        public void build(int node, int start, int end, int[] data) {
            if (start == end) {
                tree[node] = data[start];
                return;
            }
            int mid = (start + end) / 2;
            build(node * 2 + 1, start, mid, data);
            build(node * 2 + 2, mid + 1, end, data);
            tree[node] = Math.min(tree[node * 2 + 1], tree[node * 2 + 2]);
        }

        // 应用懒惰标记
        private void apply(int node, int val) {
            tree[node] -= val;  // 减去高度
            lazy[node] += val;
        }

        // 下推懒惰标记
        private void push(int node) {
            if (lazy[node] != 0) {
                apply(node * 2 + 1, lazy[node]);
                apply(node * 2 + 2, lazy[node]);
                lazy[node] = 0;
            }
        }

        public void update(int l, int r, int val) {
            update(0, 0, n - 1, l, r, val);
        }

        private void update(int node, int start, int end, int l, int r, int val) {
            // 当前区间完全在更新区间内
            if (l <= start && end <= r) {
                apply(node, val);  // 直接更新并记录懒惰标记
                return;
            }

            push(node);  // 下推懒惰标记

            int mid = (start + end) / 2;
            if (l <= mid) {
                update(node * 2 + 1, start, mid, l, r, val);
            }
            if (r > mid) {
                update(node * 2 + 2, mid + 1, end, l, r, val);
            }

            tree[node] = Math.min(tree[node * 2 + 1], tree[node * 2 + 2]);
        }

        public int getMin() {
            return tree[0];  // 根节点存储全局最小值
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int times = in.nextInt();
        int[] mountains = new int[n];

        for (int i = 0; i < n; i++) {
            mountains[i] = in.nextInt();
        }

        SegmentTree st = new SegmentTree(mountains);

        for (int i = 1; i <= times; i++) {  // 注意：应该是 <= times
            int x = in.nextInt();
            int y = in.nextInt();
            int minus = in.nextInt();

            // 转换为0-index，区间[x-1, y-1]
            st.update(x - 1, y - 1, minus);

            if (st.getMin() <= 0) {
                System.out.println(i);
                return;
            }
        }

        in.close();
    }
}

更新利用线段树的Java代码，部分依靠deepseek进行了修正

发表于 2025-10-10 15:18:51 回复(0)

Java

只需略微出手便可拿下Java的一根毛

一开始没考虑减完之后小于0的数，只能通过2个用例，改为Nums[L - 1] <= 0通过；

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

int[] nums = new int[n];

for (int i = 0; i < n; i++) {

nums[i] = in.nextInt();

}

int count = 1;

boolean bool = false;

for (int i = 0; i < m; i++) {

int L = in.nextInt();

int R = in.nextInt();

int h = in.nextInt();

while (L <= R) {

nums[L - 1] = nums[L - 1] - h;

if (nums[L - 1] <= 0) {

bool = true;

break;

}

L++;

}

if (bool == false) {

count++;

} else {

System.out.println(count);

break;

}

发表于 2025-09-17 16:19:49 回复(0)

牛客723899313号

#include <iostream>

#include <vector>

using namespace std;

int main() {

// int a, b;

// while (cin >> a >> b) { // 注意 while 处理多个 case

// cout << a + b << endl;

// }

int n,m;cin>>n>>m;

vector<int> data(n);

for(int i = 0;i<n;i++)cin>>data[i];

int flag = 1,ans = 0;int q,z,h;

for(int i = 0;i<m;i++)

{

cin>>q>>z>>h;

for(int j = q - 1;j<z;j++)

{

data[j] -= h;

if(data[j]<=0)

{

flag = 0;ans = i+1;

break;

}

if(flag == 0) break;

}

cout<<ans;

}

// 64 位输出请用 printf("%lld")

发表于 2025-08-20 21:04:46 回复(0)

偶就要搞开发

kpi笔试

发表于 2025-10-04 14:55:50 回复(0)

文明_朽木自雕


public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int shuhcu;

        int [] shan= new int[n];

        for(int i=0;i<n;i++){
            shan[i]= in.nextInt();
        }

        int [][] cishu= new int[m][3];
        for(int i=0;i<m;i++){
            cishu[i][0]= in.nextInt();
            cishu[i][1]= in.nextInt();
            cishu[i][2]= in.nextInt();
        }


        shuhcu=shifa(shan,cishu,m);

        System.out.print(shuhcu);
    }

    static int shifa(int shan[],int shifa[][],int m){
        for(int i=0;i<m;i++){
            shifacaozuo(shan,shifa[i][0],shifa[i][1],shifa[i][2]);

            for(int panduan :shan){
                if(panduan<=0){
                    return i+1;
                }
            }
        }

        return -1;
    }

    static void shifacaozuo(int shan[],int L,int R,int H){
        for(int j=L-1;j<R;j++){
            shan[j]=shan[j]-H;
        }
    }


} return -1;
} static void shifacaozuo(int shan[],int L,int R,int H){ for(int j=L-1;j<R;j++){ shan[j]=shan[j]-H;
    }
}

发表于 2025-09-17 17:38:04 回复(0)

YUANDK

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        int[] diff = new int[n + 1];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            if (i == 0) {
                diff[i] = arr[i];
            } else {
                diff[i] = arr[i] - arr[i - 1];
            }
        }
        boolean flag = true;
        for (int i = 0; flag && i < m; i++) {
            int left = in.nextInt();
            int right = in.nextInt();
            int h = in.nextInt();
            diff[left - 1] -= h;
            diff[right] += h;
            int sum = 0;
            for (int j = 0; j < right; j++) {
                sum = sum + diff[j];
                if (sum <= 0) {
                    System.out.println(i + 1);
                    flag = false;
                    break;
                }
            }
        }
    }
}

发表于 2025-08-28 11:04:15 回复(0)

C++

想五点下班勇士希望奇迹发生

这真的是较难题吗。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int ans=0;
    for(int i=0;i<m;i++)
    {
        int L,R,h;
        cin>>L>>R>>h;
        if(ans)
        continue;
        for(int j=L;j<=R;j++)
        if((a[j]-=h)<=0)
        ans=i+1;
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2025-08-03 14:37:21 回复(4)

提交观点

问题信息

线段树小米集团

难度：

7条回答 25收藏 347浏览

移山

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题