链接：

 

题意：

给定一个长度为n的01串，选一个长度至少为L的连续子串，使得子串中数字的平均值最大。

如果有多解，子串长度应尽量小；如果仍有多解，起点编号尽量小。序列中的字符编号为1～n，

因此[1,n]就是完整的字符串。1≤n≤100000，1≤L≤1000。

例如，对于如下长度为17的序列00101011011011010，如果L=7，最大平均值为6/8

（子序列为[7,14]，其长度为8）；如果L=5，子序列[7,11]的平均值最大，为4/5。

 

分析：

数形结合。

先求前缀和Si=A1+A2+…+Ai（规定S0=0），然后令点Pi=(i, Si)，则子序列i～j的平均值为

(Sj-S(i-1))/(j-i+1)，也就是直线P(i-1)Pj的斜率。这样可得到主算法：从小到大枚举t，

快速找到t'≤t-L，使得Pt'Pt斜率最大。

对于给定的t，要找的点Pt'在Pt的左边。假设有3个候选点Pi、Pj、Pk，下标满

足i<j<k<t，并且3个点成上凸形状（Pj为上凸点），则Pj一定不是最优点，

换句话说，只要出现上凸的情况，上凸点一定可以忽略。

 

假设已经有了一些下凸点，现在又加入了一个点，可能会使一些已有的点变为上凸点，

这时就应当将这些上凸点删除。由于被删除的点总是原来的下凸点中最右边的若干个连续点，

所以可以用队列来实现。

 

得到下凸线之后，对于任何一个点Pt来说，最优点Pt'都在切点，

如何求切点呢？随着t的增大，斜率也是越来越大，所以每次求出的t'只会增大，不会减小。

因此每次增加到斜率变小时停下来即可。

 

代码：

1 #include 
     
       2  3 const int UP = 100000 + 5; 4  5 int sum[UP], que[UP]; 6 char s[UP]; 7  8 //L~R 的平均值为 (sum[R]-sum[L-1])/(R-L+1) 9 inline int compare(int x1, int x2, int x3, int x4){ //比较 x1~x2 与 x3~x4 的平均值10     return (sum[x2]-sum[x1-1]) * (x4-x3+1) - (sum[x4]-sum[x3-1]) * (x2-x1+1);11 }12 13 int main(){14     int T;15     scanf("%d", &T);16     while(T--){17         int n, L;18         scanf("%d%d%s", &n, &L, s + 1);19 20         for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + s[i] - '0';21 22         int head = 0, tail = 0, ansL = 1, ansR = L;23 24         //que[head...tail] 为候选左端点队列25         for(int i = L; i <= n; i++){ //枚举右端点26             while(tail - head > 1 && //删除上凸点27                   compare(que[tail-2], i-L, que[tail-1], i-L) >= 0) tail--;28             que[tail++] = i - L + 1; //新的候选点29 30             while(tail - head > 1 && //更新切点31                   compare(que[head], i, que[head+1], i) <= 0) head++;32 33             int res = compare(que[head], i, ansL, ansR);34             if(res > 0 || res == 0 && ansR - ansL > i - que[head]){35                 ansL = que[head];  ansR = i;36             }37         }38         printf("%d %d\n", ansL, ansR);39     }40     return 0;41 }