很妙的贪心。
最开始的平均数是固定的，我们设为 $\overline a$。直接求极差很不方便，我们考虑求所有操作中使 $\overline a’$ 向两边分别偏移了多少。
我们考虑 $i$ 次操作之后，还剩下一个长度为 $n-i$ 的 $[l,r]$ 的序列。我们容易发现对于最优解的情况，去掉两边元素之后得到的区间 $[l_1,r_1],[l_2,r_2]$，分别满足为最大的 $\overline a_{l_1,r_1}\le \overline a$ 和最小的 $\overline a_{l_2,r_2}\ge \overline a$。 否则，将当前区间向左或向右平移，一定可以得到更优的答案。
直接处理出这样的 $[l_1,r_1],[l_2,r_2]$。根据上面的推论，我们每一步一定是取这两个区间之一。于是我们直接按照 $\overline a-\overline a_{l,r}$ 从大到小排序，然后枚举，直接钦定 $[l_1,r_1]$，对于 $\overline a_{l_1’,r_1’}\le \overline a_{l_1,r_1}$，我们选取所有 $[l_2’,r_2’]$ 即可。时间复杂度 $\mathcal O(n\log n)$。
Code
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
42
43
44
45
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define PDD pair<double,double>
using namespace std;
const int N=2e5+10;
const double INF=1e9,eps=1e-9;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
ll sum[N];
double ave;
PDD a[N];
inline double get(int l,int r){return 1.0*(sum[r]-sum[l-1])/(r-l+1);}
int main()
{
read(n);
for(int i=1,x;i<=n;i++)read(x),sum[i]=sum[i-1]+x;
ave=1.0*sum[n]/n;
int l=1,r=n;
for(int i=1;i<=n;i++)
{
l++;
if(get(l,r)>ave)l--,r--;
a[i]={ave-get(l,r),get(l+1,r+1)-ave};
}
sort(a+1,a+n);
double ans=INF,res=0;
for(int i=n-1;i;i--)ans=min(ans,a[i].first+res),res=max(res,a[i].second);
printf("%.10lf\n",ans);
return 0;
}
|