/ Vijos / 题库 /

子串平均值

子串平均值

时间限制:1秒  内存限制:256M


【题目描述】

  给定一个长度为 \(n\) 的 01 串,选一个长度至少为 L 的连续子串,使得子串中数字平均值最大。如果有多解,子串长度应尽量小;如果仍然有多解,起点编号应尽量小。序列中的字符编从左到右依次编号为 \(1..n\),因此 \([1,n]\) 就是完整的字符串。

  例如,对于如下长度为 17 的序列 00101011011011010,如果 \(L=7\),最大平均值为 6/8(子序列为 [7,14],其长度为8 );如果 \(L=5\),子序列为 [7,11] 的平均值最大为 4/5。

【输入格式】

  第包含两行,第 1 行是 \(n\) 和 \(L\),第 2 行长度为 \(n\) 的 01 串。

【输出格式】

  包含 2 个整数,第一行最大平均值,用最简分数表示,格式如样例;第2行的两个整数表示平均值最大序列的起点和终点。

【输入输出样例1】

 Input

17 5
 00101011011011010

 Output

4/5
7 11

【输入输出样例2】

 Input

20 4
 11100111100111110000

 Output

1/1
6 9

【数据限制】

  对于 \(100\%\) 的数据,\(1≤n≤1000000\),\(1≤L≤1000\)。

【来源】

  Mr.he

信息

ID
2744
难度
(无)
分类
其他 | 二分查找动态规划 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者