摘要：数形结合，斜率优化，单调队列。

题意：求一个长度为n的01串的子串，子串长度至少为L，平均值应该尽量大，多个满足条件取长度最短，还有多个的话，取起点最靠左。

求出前缀和S[i]，令点Pi表示(i,S[i])，那么这个问题就转化成了求斜率最大的两点。画图分析可知，如果有上凸点，那么上凸点，一定不会是最优的，所以问题就变成了维护一个下凸的曲线。那么可以通过比较斜率来维护，而要求切点，在上一个切点之前的点不会得到更优的解。

假设在A点，即之前的切线之上，那么选切点以前的点，一定不是最优的，假设在B点，原来的切线之下，那么，怎么也得不到一个斜率比之前切线更大的线。

更具体得可以看这篇论文：

 

#include
     
      using namespace std;const int maxn = 1e5+233;char s[maxn];int sum[maxn],q[maxn];#define seg(x1,x2) (sum[x2]-sum[x1-1])inline int cmp_ave(int x1,int x2,int x3,int x4){    return seg(x1,x2)*(x4-x3+1) - seg(x3,x4)*(x2-x1+1);}int main(){    //freopen("in.txt","r",stdin);    int T; scanf("%d",&T);    while(T--){        int n,L;        scanf("%d%d%s",&n,&L,s+1);        sum[0] = 0;        for(int i = 1; i <= n; i++)            sum[i] = sum[i-1] + s[i] - '0';        int ansL = 1, ansR = L;        int i = 0,j = 0;        for(int t = L; t <= n; t++){            while(j-i>1 && cmp_ave(q[j-2],t-L,q[j-1],t-L) >= 0)j--;            q[j++] = t-L+1;            while(j-i>1 && cmp_ave(q[i],t,q[i+1],t) <= 0) i++;            int c = cmp_ave(q[i],t,ansL,ansR);            if(c > 0|| c == 0 && t-q[i] < ansR - ansL){                ansL = q[i]; ansR = t;            }        }        printf("%d %d\n",ansL,ansR);    }    return 0;}
     

 整理以下：以后遇到求(Pi-Pj)/(i-j)形的式子求最大值，就可以套用这个模版了。。。