谢罪，题目顺序有点问题，这题得放T4。

---

【ZSROI R1-C 完美计算】

题目大意：

题目除开第一句话够简洁了。

---

$20pts:$

暴力求 $i,j,k$，时间复杂度 $O(n^3)$。

$40pts:$

暴力求 $i,j$，注意到分子部分其实是可以弄成前缀和，定义 $s_i$ 表示 $\sum_{j=1}^i a_j^2$。答案变为下式

$$\frac{s_j-s_i}{j^2-i^2}(0\le i<j\le n)$$

时间复杂度 $O(n^2)$

该子任务的 $s_i$ 后面还要用

$测试点5:$

$max$ 值为 $1$，$min$ 值为 $\frac{1}{2n-1}$

$100pts:$

本题有两种满分做法。

• 斜率做法

考虑在平面直角坐标系上建点，若要求出所有点其中两个点组成直线斜率的最小值（可以形象地理解为最为平坦，如图1），可以得出性质：只有在纵坐标相邻的两个点组成直线的斜率才有可能是最小值。 如图2 。

---

回归题目，把 $(i^2,s_i)$ 建点，并将原式子转化为下式

$$\frac{\sum_{k=i}^j a_k^2}{j^2-(i-1)^2}=\frac{s_j-s_{i-1}}{j^2-(i-1)^2}$$

而点 $((i-1)^2,s_{i-1})$ 与点 $(j^2,s_j)$ 组成的直线的斜率 $k$ 为：

$$k=\frac{y_2-y_1}{x_2-x_1}=\frac{s_j-s_{i-1}}{j^2-(i-1)^2}$$

发现原式子就是求点 $((i-1)^2,s_{i-1})$ 与点 $(j^2,s_j)$ 组成的直线的斜率。因为平方具有非负性，所以 $a_i^2$ 一定非负，所以 $s_i$ 一定单调递增，那么求 $min$ 值只需要考虑相邻两点，即求出下式

$$\min \frac{a_i^2}{i^2-(i-1)^2}$$

可以求出。若最小值是 $\frac{a}{b}$，则最大值就是 $\frac{b}{a}$，等价于把横纵坐标倒过来，$s_i$ 依旧递增，那相同的方法可做。

#include<bits/stdc++.h>		
#define int long long		
using namespace std;		
int n,a[100009];		
double mx = -1e18,mn = 1e18;		
signed main(){		
	cin>>n;	
	for(int i = 1;i<=n;++i){	
		cin>>a[i];
		a[i]*=a[i];
        a[i]+=a[i-1];		
	}	
	for(int i = 1;i<=n;++i){	
		double p = (double)(a[i]-a[i-1])/(i*i-(i-1)*(i-1));
		mx = max(mx,p);
		mn = min(mn,p);
	} 	
	printf("%.3f %.3f",mx,mn);	
}		

时间复杂度：$O(n)$

---

• 单调队列+二分

具体的思路和上面有联系，这里不再叙述。

使用一个单调队列，每次队头二分，分别考虑 $\max,\min$ （参考斜率优化DP），剩下模板。

#include <bits/stdc++.h>		
using namespace std;		
#define int long long		
int a[100009],sum[100009],q[100009];		
double slope(int i,int j){		
	return 1.0*(sum[j]-sum[i])/(j*j-i*i);	
}		
int solve(int L,int R){		
	int l = L,r = R;	
	while(l<=r){	
		int mid = l+r>>1;
		if(slope(q[mid],q[mid+1])>=slope(q[mid+1],q[mid+2])) r = mid-1;
		else l = mid+1;
	}	
	return l-1;	
}		
signed main(){		
	int n;	
	cin>>n;	
	for(int i = 1;i<=n;++i){	
		cin>>a[i];
		sum[i] = sum[i-1]+a[i]*a[i];
	}	
	int l = 0,r = 0;	
	double mx = 0.0;	
	for(int i = 1;i<=n;++i){	
		int ans = solve(l,r);
		mx = max(mx,slope(i,q[ans]));
		while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) r--;
		q[++r] = i;
	}	
	for(int i = 1;i<=n;++i){	
		mx = max(mx,1.0*a[i]*a[i]/(2*i-1));
    }		
	l = 0,r = 0;	
	double mn = 1e18;	
	for(int i = 1;i<=n;++i){	
		int ans = solve(l,r);
		mn = max(mn,slope(i,q[ans]));
		while(l<r&&slope(q[r-1],q[r])<=slope(q[r],i)) r--;
		q[++r] = i;
	}	
	for(int i = 1;i<=n;++i){	
		mn = min(mn,1.0*a[i]*a[i]/(2*i-1));
    }		
	printf("%.3f %.3f",mx,mn);	
}		

时间复杂度：$O(nlogn)$