( t{udebug})真好用！
这道题用到了斜率优化的思想（然而汝佳说这是“数形结合”）。
如果有《算法竞赛入门经典》，那么你可以看一下(P243)，上面有较为详细的讲解。
大体思路是将一段区间([i,j])看成是坐标分别为((i,sum_{1,i}))和((j,sum{1,j)})的两点，然后平均数就是这两个点所成直线的斜率。
这里主要说一下代码实现
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
LL read() { //快读
int k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k*10+c-48, c=getchar();
return k*f;
}
int read_c() { //快读01串
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '1') break;
return c - 48;
}
double sum[100010], q[100010]; //sum是前缀和，q是单调队列
int calc(int x1, int y1, int x2,int y2) { //比较前两个点和后两个点的斜率 取名x,y只是为了下面好看一点……
return (sum[y1]-sum[x1-1]) * (y2-x2+1) - (sum[y2]-sum[x2-1]) * (y1-x1+1);
}
int main() {
int t = read();
while(t--) {
int n = read(), l = read();
for(int i = 1; i <= n; ++i) sum[i] = sum[i-1] + read_c(); //前缀和处理
int ansl = 1, ansr = l, h = 0, t = 0; //ansl,ansr是答案区间 h,l是队头和队尾
for(int i = l; i <= n; ++i) { //枚举右端点 单调队列里是左端点
while(t - h > 1 && calc(q[t-2], i-l, q[t-1], i-l) >= 0) --t;
//队列里至少要有两个元素才有法比 i-l+1是要新加进去的左端点(因为区间长度最小为l)，之后我们删队头，至少要留下i-l
// --t 是要删除上凸点
q[t++] = i - l + 1; //将新的左端点入队
while(t - h > 1 && calc(q[h+1], i, q[h], i) >= 0) ++h;
//当前枚举的右端点i的左端点为q[h]，为了保证结果最优，应删掉队首所有的下凸点
int flag = calc(q[h], i, ansl, ansr); //将当前最优值和答案比较
if(flag > 0 || (flag == 0 && i-q[h] < ansr-ansl)) //更新答案
ansl = q[h], ansr = i;
}
printf("%d %d
", ansl, ansr);
}
return 0;
}