题意：给定一段01序列，求一段长度不小于L的连续序列，使其平均值最大
思路：一看就想到了斜率优化，但是用基本的推公示一直没推出来，看了别人的代码，像推出斜率的式子一直没弄出来。。后来一看别人写的题解，原来是数形结合可以推出斜率单调。然后维护一个下凹的队列（斜率要递增）。至于为什么这么做，可以吧sum[i]（把开头到当前的和）看作纵坐标，i当作横坐标，然后做出图，就会发现实际上就是找横坐标之差大于等于L的点形成直线斜率最大。那么在纸上画一下，结论就很明显了。。
当然，出了这种方法外，还有二分最大斜率，然后在判定的方法。。(判定时把每个数减去，斜率，接着用类似最大子序列合的方法，这种方法具体我没写过，不过有人好像就是这样过的)
不过想想，其实两种本质上应该是一种，只不过求斜率的方法一个O(1),一个log(N)而已
---------不懂看一下周源大神的论文《浅谈数形结合思想在信息学竞赛中的应用》讲的很明白
ps.poj2018也是同样的题，有空再去写一下了。
**********************************************************************
/*
* Author: yzcstc
* Created Time: 2013/8/18 0:35:49
* File Name: uval4726.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<utility>
#define M0(x) memset(x, 0, sizeof(x))
#define Inf 0x7fffffff
#define PB push_back
#define SZ(v) ((int)(v).size())
#define eps 1e-8
using namespace std;
int n , L, TT;
int Y[], q[]; double ratio(int i, int j){
return i == j ? Inf : (Y[j] - Y[i] + 0.0)/(j - i + 0.0);
} void solve(){
scanf("%d%d", &n, &L);
Y[] = ;
for (int i = ; i <= n; ++i){
scanf("%1d", &Y[i]);
Y[i] += Y[i-];
}
M0(q);
int l = , r = , ansl = , ansr = n;
double ans = -;
for (int i = L; i <= n; ++i){
while (l < r && ratio(q[r - ], q[r]) >= ratio(q[r - ], i - L)) --r;
q[++r] = i - L;
while (l < r && ratio(q[l], i) <= ratio(q[l + ], i)) ++l;
if (ans + eps < ratio(q[l], i) || fabs(ans - ratio(q[l], i)) < eps && i - q[l] < ansr - ansl){
ans = ratio(q[l], i);
ansl = q[l];
ansr = i;
}
}
printf("%d %d\n", ansl + , ansr);
} int main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d", &TT);
while (TT--){
solve();
}
// fclose(stdin); fclose(stdout);
return ;
}