Java教程

经典算法题--给指定编号区间的小朋友发糖

本文主要是介绍经典算法题--给指定编号区间的小朋友发糖,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
# 有n个小朋友,从1到n编号。
# 老师给小朋友们发糖,每次给编号在[s,r]内的每个小朋友一颗糖。
# 已知每个小朋友在最开始都是有0颗糖,老师一共发了m次糖,求此时每个小朋友各有几颗糖
#
# 输入:第一行输入n和m
# 接下来m行,每行给出2个数,s与r,标定区间
# 输出:n个整数,即老师给了m次糖以后每个小朋友各有几颗糖

 1 n,m = list(map(int,input().strip().split()))
 2 arr = [0] * n
 3 for i in range(m):
 4     s,r = list(map(int,input().strip().split()))
 5     arr[s-1] += 1
 6     if r!= n:
 7         arr[r] -= 1
 8 for i in range(1,n):
 9     arr[i] = arr[i-1]+arr[i]
10 
11 print(' '.join(map(str,arr)))

 

分析:这是个典型的区间更新+单点查询的题型

这种题目下,当在[s,r]区间内每个数加1,在左端点处+1,在右端点后一位(r+1)处减去1,如此查询点被覆盖多少次,求出前缀的和即可

这篇关于经典算法题--给指定编号区间的小朋友发糖的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!