题意
求长度为n的01串中1占总长（大于L）的比例最大的一个子串起点和终点。
分析
前缀和s[i]保存前i个数有几个1，[j 1,i] 这段区间1的比例就是(s[i]-s[j])/(i-j)，于是问题转换为找斜率最大的两个点。
如图，加入j时，就要去掉b1、b2，才能维护斜率的单调递增。
以队列里的点做起点，i 结尾的线段斜率最大的是 i和队列里点组成的下凹线的切线。切点前的点就不会再用到了，因为i后面的点和他们的斜率也将不如和这个切点的斜率。
数形结合，斜率优化，单调队列。
代码
代码语言：javascript复制#include<deque>
#include<cstdio>
using namespace std;
deque<int> q;
int s[100005];
int ansl,ansr;
int great(int a,int b,int c,int d)//求ab斜率是否大于cd斜率
{
return (s[a]-s[b])*(c-d) - (s[c]-s[d])*(a-b);
}
int main()
{
int t,L,n,a;
scanf("%d",&t);
while(t--)
{
scanf("%d%d ",&n,&L);
char cc;
for(int i=1;i<=n;i ){
cc=getchar();
s[i]=s[i-1] cc-'0';//这样读才不会超时
}
q.clear();
ansl=0;
ansr=L;
for(int i=L; i<=n; i )//以i做线段右端点
{
int j=i-L;
while(q.size()>1)//把j作为线段左端点，加入单调队列
{//（单调指斜率单调递增）
int b1=q[q.size()-1];//倒数第1个
int b2=q[q.size()-2];//倒数第2个
if(great(b1,b2,j,b1)>0)//如果b1b2斜率比jb1更大
q.pop_back();//弹出b1，维护单调性
else break;//
}
q.push_back(j);//j入队
while(q.size()>1)//去掉队前头不优的起点（线段左端点）
{//因为和i斜率最大的是下凹线的切点，切点前的点不优
if(great(i,q[0],i,q[1])<=0)//以i做终点 q[0]i的斜率小于q[1]i的斜率
q.pop_front();//就弹出队头
else break;
}
int tmp=great(i,q[0],ansr,ansl);//i和切点的斜率，也就是最大斜率
if(tmp>0 || tmp==0 && i-q[0]<ansr-ansl)
{
ansl=q[0];//左端点更新
ansr=i;//右端点更新
}
}
printf("%d %dn",ansl 1,ansr);//存的是左端点右1的点，故输出时 1
}
return 0;
}
