TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3604
  • 题目
  • P3604平均值
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    给定一个长度为n的01串,选一个长度至少为L的连续子串,使得子串中数字的平均值最大。
    如果有多解,子串长度应尽量小;如果仍有多解,起点编号尽量小。
    序列中字符编号1到n,1<=n<=300000, 1<=L<=3000.

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

    输入格式

    第一行,两个整数n和L
    第二行,一个长度为n的01序列

    输出格式

    一行,两个整数,表示所选子序列的起点和终点

    样例输入

    样例输入1:
    17 5 
    00101011011011010 

    样例输入2:
    20 4 
    11100111100111110000

    样例输出

    样例输出1:
    7 11 

    样例输出2:
    6 9


    来源  uva1451