私信TA

用户名:Praguetramp

访问量:29250

签 名:

等  级
排  名 19
经  验 19923
参赛次数 0
文章发表 130
年  龄 0
在职情况 待业
学  校
专  业

  自我简介:

aura

解题思路:    利用差分数组的思想,意思就是分界出各段的差值

注意事项:    O(n^2)的循环不会通过

参考代码:

import java.util.Scanner;
/**
 * 2021年2月21日 下午2:30:18
 * 
 * @author praguetramp
 * 	小朋友排成一排,老师给他们分苹果。
	小朋友从左到右标号1..N。有M个老师,每次第i个老师会给第Li个到第Ri个,一共Ri-Li+1个小朋友每人发Ci个苹果。
	最后老师想知道每个小朋友有多少苹果。
	差分数组,最后前后两项求和
	输入:5 3
		1 2 1
		2 3 2
		2 5 3
	输出:1 6 5 3 3 
	差分:[0, 1, 5, -1, -2, 0, -3]  负号即为同数目的分界点
 */
public class P1501 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int num[] = new int[n + 2];

		for (int i = 0; i < m; i++) {
			int li = in.nextInt();
			int ri = in.nextInt();
			int ci = in.nextInt();
			num[li] += ci;
			num[ri + 1] -= ci;
		}
		for (int i = 1; i <= n; i++) {
			num[i] += num[i - 1];
			System.out.print(num[i] + " ");
		}
		in.close();
	}

}


 

0.0分

0 人评分

  评论区