UVA 1451 Average平均值 （数形结合，斜率优化）

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

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

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

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

更具体得可以看这篇论文：浅谈数形结合思想在信息学竞赛中的应用

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+;

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+) - seg(x3,x4)*(x2-x1+);

}

int main()

{

    //freopen("in.txt","r",stdin);

    int T; scanf("%d",&T);

    while(T--){

        int n,L;

        scanf("%d%d%s",&n,&L,s+);

        sum[] = ;

        for(int i = ; i <= n; i++)

            sum[i] = sum[i-] + s[i] - '';

        int ansL = , ansR = L;

        int i = ,j = ;

        for(int t = L; t <= n; t++){

            while(j-i> && cmp_ave(q[j-],t-L,q[j-],t-L) >= )j--;

            q[j++] = t-L+;

            while(j-i> && cmp_ave(q[i],t,q[i+],t) <= ) i++;

            int c = cmp_ave(q[i],t,ansL,ansR);

            if(c > || c ==  && t-q[i] < ansR - ansL){

                ansL = q[i]; ansR = t;

            }

        }

        printf("%d %d\n",ansL,ansR);

    }

    return ;

}

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