这是个近似算法。

\(O(n^2)\) 做法很裸,就是直接枚举 \(k\) ,然后 \(O(n)\) 得到最小极差。

注意到答案是不降的,只要求近似解。我们可以在误差允许的情况下,连续的一段都用一个数近似。

具体实现就是像线段树搞搞… 复杂度大概是 \(O(n \log_{1.05} V)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,a[maxn],f1[maxn][20],f2[maxn][20],_lg2[maxn],ans[maxn];

int getMin(int L,int R){
int t=_lg2[R-L+1];
return min(f1[L][t],f1[R-(1<<t)+1][t]);
}
int getMax(int L,int R){
int t=_lg2[R-L+1];
return max(f2[L][t],f2[R-(1<<t)+1][t]);
}
void Calc(int k){
for(int i=1;i<=n-k+1;i++) ans[k]=min(ans[k],getMax(i,i+k-1)-getMin(i,i+k-1));
}
void Solve(int L,int R){
if(R-L<=1) return;
if(floor(1.05*ans[L])>=ceil(ans[R]*0.95)){
for(int i=L+1;i<=R-1;i++) ans[i]=floor(1.05*ans[L]);
return;
}
int mid=(L+R)>>1;
Calc(mid); Solve(L,mid); Solve(mid,R);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]), f1[i][0]=f2[i][0]=a[i];
for(int i=1;i<=n;i++) _lg2[i]=log2(i);
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n-(1<<j)+1;i++){
f1[i][j]=min(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
f2[i][j]=max(f2[i][j-1],f2[i+(1<<j-1)][j-1]);
}
for(int i=1;i<=n;i++) ans[i]=2e9;
Calc(2); Calc(n); Solve(2,n);
for(int i=2;i<=n;i++) printf("%d\n",ans[i]);
}