这道题用了数形结合， 真的牛逼， 完全想到不到还可以这么做
因为题目求的是平均值， 是总数除以个数， 这个时候就可以联系
到斜率， 也就是说转化为给你一堆点， 让你求两点之间的最大斜率
要做两个处理
（1）去掉上凸点， 因为上凸点是无论如何都不会为最优解的
（2）去掉之后每两个点之间的斜率是单调递增的， 这个时候要求切点。
切点即最大斜率， 所以就枚举终点， 然后找该终点对应的最大斜率
（也就是找到切点）， 然后更新答案。
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112345;
int sum[MAXN], p[MAXN], n, L;
char s[MAXN];inline int compare_average(int x1, int x2, int x3, int x4) //比较斜率
{return (sum[x2]-sum[x1-1]) * (x4-x3+1) - (sum[x4]-sum[x3-1]) * (x2-x1+1);
}int main()
{int T;scanf("%d", &T);while(T--){scanf("%d%d%s", &n, &L, s+1); //s+1从位置一开始输入 sum[0] = 0;REP(i, 1, n + 1) sum[i] = sum[i-1] + s[i] - '0';int ansL = 1, ansR = L, i = 0, j = 0; //i到j这个区间代表去掉之后留下的有用的点REP(t, L, n + 1){while(j - i > 1 && compare_average(p[j-2], t-L, p[j-1], t-L) >= 0) j--; //去掉上凸点 p[j++] = t - L + 1;while(j - i > 1 && compare_average(p[i], t, p[i+1], t) <= 0) i++; //去掉切点之前的点 int c = compare_average(p[i], t, ansL, ansR); //更新答案 if(c > 0 || c == 0 && t - p[i] < ansR - ansL){ansL = p[i];ansR = t;} }printf("%d %d\n", ansL, ansR);}return 0;
}