题解 P1419 【寻找段落】

· · 题解

看到题解里都是 O(N\log N)的做法，这里提供一种 O(N) 的做法，目前是洛谷 Rank1

已更新图源为洛谷图床

题目要求平均值最大，其实就是 \frac{s_{j+1}-s_i}{j-i+1} 最大，其中 s_i=\sum_{k=1}^ia_k 。
为了方便，我们令 T=j+1 ，即求 \frac{s_T-s_i}{T-i}\rightarrow \frac{s_j-s_i}{j-i}
这个式子可以看成一个斜率的表达式，下面联系数形结合来讲

考虑下面情况：我们已经在图中加入了三个点 P_i,P_j,P_k，现在我们要考虑点 P_t(t>j) 的贡献

结合图：

(图丑勿怪)

为了表述方便，我们令 Slope(P_i,P_j) 表示 P_i 和 P_j 两点所构成的直线的斜率，显然，答案为 \max\{Slope(P_i,P_j),i\neq j\}

下面我们讨论加入点 P_t 时的情况

  1. 若 Slope(P_j,P_t)>Slope(P_i,P_t) 则点 P_t 将落在区域 S_1
  2. 若 Slope(P_j,P_t)>Slope(P_k,P_t) 则点 P_t 将落在区域 S_2

如果我们需要让点 P_t 和 P_j 这段区域来更新答案
则 Slope(P_j,P_t) 必须同时大于 Slope(P_i,P_t) 和 Slope(P_k,P_t)

由图可知，点 P_t 应该落在重叠区域 S_3 ，显然不符合我们 t>j 的前提要求

因此任意一个合法的 P_t 都不可能与 P_j 组成一条更优的直线。

这次讨论告诉我们：对于任意的点 P_t ，都不可能存在一个上凸点 P_j 使得 Slope(P_j,P_t) 成为最终的答案，因此我们可以把图像中所有的上凸点全部删除，剩下的就是一个下凸壳

下面我们要考虑如何更新答案：

如下图

与 P_t 更新答案的点显然是 P_3，因为这个点是与下凸壳相切的，过点 P_t 的直线上的一点

然后我们考虑下一个点 P_t'

显然，对于 P_3,P_4 来说
因为 Slope(P_3,P_t)>Slope(P_4,P_t)
所以 Slope(P_3,P_t')>Slope(P_4,P_t')
这一点可以从图中看出来

因此，我们同样可以把 P_4 从图像中删除，至此，我们已经得到了一个时空复杂度均为 O(N) 的算法

流程如下：

1.对点 t ，通过弹出队头的方法来寻找过点 t 且与下凸包相切的点 p，更新答案
2.对点 t ，通过弹出队头的方法来删除与点 t 距离超过 T 的点（保证了子串长度  <= T）
3.加入点 t-S+1（保证了子串长度 >= S），此时有可能使图像的下凸性丧失，将队尾丧失下凸性的点弹出
4.执行下一个点 t'(回到 1)

代码如下 :

#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
int read(){int x=0,f=0;char ch=0;while(!isdigit(ch))f|=(ch=='-'),ch=getchar();while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar();return f?-x:x;}
void Ot(int x){if(x<0)putchar('-'),x=-x;if(x>=10)Ot(x/10);putchar(x%10+48);}
void Print(int x,char til='\n'){Ot(x);putchar(til);}
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
int Abs(int x){return x<0?-x:x;}
const int MAXN=3000500;
int n,a[MAXN],s,t;
int sum[MAXN];
int head,tail;
int q[MAXN];
double Slope(int x,int y){return 1.0*(sum[y]-sum[x])/(y-x);}
signed main(){
    n=read();s=read(),t=read();
    for(reg int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];
    double ans=0;
    head=tail=0;
    q[tail++]=0;
    for(reg int i=s;i<=n;i++){
        while(head+1<tail&&(Slope(q[head],i)<Slope(q[head+1],i)||i-q[head]+1>t))head++;
        ans=max(ans,Slope(q[head],i));
        int j=i-s+1;
        while(head+1<tail&&Slope(q[tail-1],j)<Slope(q[tail-2],q[tail-1]))tail--;
        q[tail++]=j;
    }
    printf("%.3lf\n",ans);
    return 0;
}

摘用一段话：

回顾本题的解题过程，一开始就确立了以平面几何为思考工具的正确路线，很快就发现了检查集合中对最优解有贡献的点构成一个下凸函数这个重要结论，之后借助计算几何中求凸包的方法维护一个下凸折线，最后还利用下凸函数斜率的单调性发现了找切线简单方法。题解围绕平面几何这个中心，以斜率为主线，整个解题过程一气呵成，又避免了令人头晕的代数式变换，堪称以形助数的经典例题。

https://wenku.baidu.com/view/b97cd22d0066f5335a8121a3.html

附：部分证明源于论文《浅谈数形结合思想在信息学竞赛中的应用》，地址：https://wenku.baidu.com/view/b97cd22d0066f5335a8121a3.html