#yyds干货盘点# 动态规划专题：差分

wander lv.2

发布时间：2023-12-03 21:05:07 224

相关标签：

1.简述：

描述

给你一个长度为n的正数数组.接下来对这个数组进行m次操作，每个操作包含三个参数l,r,k，代表将数组中部分都加上k。请输出操作后的数组。

输入描述：

第一行包含两个整数n和m。第二行包含n个整数表示接下来是m行，每行三个整数，分别代表每次操作的参数l,r,k.

输出描述：

输出1行，表示m次操作后的

示例1

输入：

输出：

5 6 1

2.代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //存放数组元素
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        //存放增量
        long[] delta=new long[n+1];
        //m次操作
        while(m-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            int k=sc.nextInt();
            //进行差分处理
            delta[l]+=k;
            if(r>=n) continue;
            delta[r+1]-=k;
        }
        
        //计算对应元素增量
        for(int i=0;i<n;i++){
            delta[i+1]+=delta[i];
            System.out.print(delta[i+1]+arr[i]+" ");
        }
            
    }
}

文章来源： https://blog.51cto.com/u_15488507/5853663

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。