8-9 Average
紫薯 P-243
题意 ：一个N长度的01串，求一段不小于L长度子串的最大平均值
数形结合(好像很厉害….)
先求前缀 然后就转换成了 求 (sum[ j ] -sum [ i ] )/( j -i )的最大值 O方过不了，仔细一看就是求 N个点中斜率最大的一段 图在书上 8-16 书上解释也很清楚,就是 每次找3个点 发现，每次为凸形时那个凸形的点无效，不可能比边上点大，这样会去除大不部分点
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define inf 0x3f3f3f3f
int sum[N];
int num[N];
int slove(int x1,int x2,int x3,int x4)
{return (sum[x2]-sum[x1])*(x4-x3)-(sum[x4]-sum[x3])*(x2-x1);
}
int main()
{int t;cin>>t;while(t--){int n,L;cin>>n>>L;string s;cin>>s;sum[0]=0;s=" "+s; //处理从0开始,因为sum[j]-sum[i]如果数组从0开始，就永远用不到第一个点，都会把它减掉(WA了无数发，才发现...)for(int i=1;i<s.length();i++){sum[i]=sum[i-1]+s[i]-'0';}int i=0;int j=0;int tl=0;int tr=L;for(int k=L;k<n;k++){//删除中间凸形while(i<j-1&&slove(num[j-1],k-L,num[j-2],k-L)<0) j--;num[j++]=k-L;// 处理掉前面不是最大的结果while(i<j-1&&slove(num[i],k,num[i+1],k)<=0) i++;int tt=slove(num[i],k,tl,tr);if(tt>0||(tt==0&&(k-i<tr-tl))) tl=num[i],tr=k;}cout<<tl+1 <<" "<<tr<<endl;}return 0;
}