← 返回题目列表

AtCoder · awc0094_b

B. 温度波动

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥在气象台工作,记录日平均气温。温度记录为简化的整数值,范围为 1 to 9 (9 级)。

有一天,高桥决定分析连续的温度数据 N过去的天。高桥重点关注连续的总温度 K天窗口,并且想要计算每个连续的总数 K天窗口,然后求其中最大值和最小值的差值。差异越大,说明该时期气温波动越剧烈。

具体来说,考虑到温度记录 N 天为 A_1, A_2, \dots, A_N,有 N - K + 1 连续的总值 K天窗。也就是说,对于 i = 1, 2, \dots, N - K + 1,我们计算:

S_i = \sum_{j=0}^{K-1} A_{i+j}

找出最大值和最小值之间的差异 S_1, S_2, \dots, S_{N-K+1}.

约束

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq A_i \leq 9
  • 所有输入值均为整数。

输入

N K
A_1 A_2 \dots A_N
  • 第一行包含一个整数 N 表示观察天数和一个整数 K 代表感兴趣的连续天数,以空格分隔。
  • 第二行包含整数 A_1, A_2, \dots, A_N 代表每天的温度,以空格分隔。

输出

打印最大值和最小值之间的差值 S_1, S_2, \dots, S_{N-K+1} 在一行上。


示例输入 1

5 3
2 5 3 1 4

示例输出 1

2

示例输入 2

10 4
3 1 4 1 5 9 2 6 5 3

示例输出 2

13

示例输入 3

20 5
1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9

示例输出 3

8