UVA 1451 Average 数形结合

借此把数形结合相关的知识补充补充，戳这里→浅谈数形结合思想在信息学竞赛中的应用

emmmmm求区间斜率最大的问题，用单调队列去维护下凸曲线，感觉有些博客解释的蛮清楚的，比如这里→戳

注意一下：下标的问题，还有，不要忘记初始化ansl,ansr

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e5+5;
int n,L,t,ansl,ansr;
double ans=0;
int pre_sum[MAX];
int st[MAX];
string s; 
double k(int l,int r)
{
    return (double)(pre_sum[r]-pre_sum[l-1])/(double)(r-l+1);
}
int main()
{
    cin>>t;
    while(t--){
    cin>>n>>L;
    cin>>s;
    pre_sum[0]=0;
    ans=0;
    ansl=1;ansr=n;
    for(int i=1;i<=n;i++)
    {
        if(s[i-1]=='1')
         pre_sum[i]=pre_sum[i-1]+1;
        else 
         pre_sum[i]=pre_sum[i-1];
    }
    int l=0,r=0;
    for(int i=L;i<=n;i++)
    {
        while(l<r-1&&k(st[r-1],i-L)<k(st[r-2],i-L)) r--;
        st[r++]=i-L+1;
        while(l<r-1&&k(st[l],i)<=k(st[l+1],i)) l++;
        double temp=k(st[l],i);
        if(ans<temp||temp==ans&&i-st[l]<ansr-ansl)
         {
              ansr=i;
              ansl=st[l];
              ans=temp;
        }
    }
    cout<<ansl<<" "<<ansr<<endl;
   }
    return 0;
 }