Maximum Average Subarrays

题目描述

给定一个包含 n 个整数的数组。对于每个 i = 1, 2,\dots, n，你的任务是找到以下标 i 结尾且平均值最大的子数组。如果存在多个平均值最大的子数组，应该找到最长的那个。

输入格式

第一行有一个整数 n：数组的大小。 下一行有 n 个整数 x_1, x_2,\dots, x_n：数组的内容。

输出格式

输出 n 个整数：对于每个 i = 1, 2,\dots, n，输出以下标 i 结尾且平均值最大的子数组的长度。

7
1 6 4 6 2 5 5

1 1 2 1 4 1 2

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^6$ 样例解释：考虑 i = 5。所有以下标 5 结尾的子数组的平均值分别为 $\frac{1 + 6 + 4 + 6 + 2}{5}$ = 3.8、$\frac{6 + 4 + 6 + 2}{4}$ = 4.5、$\frac{4 + 6 + 2}{3}$ = 4、$\frac{6 + 2}{2}$ = 4 和 $\frac{2}{1}$ = 2。最大的平均值是 4.5，对应子数组的长度是 4。

标签: CSES3301|附加题1

来源

CSES3301|附加题1