有一个由 \(n\) 个整数组成的数列 \(a\) 。请求出所有长度不少于 \(k\) 的子串的平均值最大为多少，保留三位小数。
注意：某一子串的平均值为子串中所有数的和除以子串的长度。
\(1\leq n\leq 3\cdot 10^5,1\leq k\leq n,1\leq a_i\leq 10^6\)
如果枚举子串的大小的话，时间复杂度无法做到 \(O(\log n)\) 或者 \(O(\log^2 n)\) .
因为是平均值，可以考虑二分，二分平均值的大小 .
这里可以直接二分小数，或者乘以 \(10000\) . 我选择后一种 .
那么，对于当前 \(mid\) ，枚举子串的右端点 \(r\) ，那么左端点 \(l\) 满足 \(r-k+1\geq l\) ，且 \(\frac{\sum\limits_{i=l}^{r} a_i}{r-l+1}\geq mid\) ，就存在一组满足条件的解 .
\[\frac{\sum\limits_{i=l}^{r} a_i}{r-l+1}\geq mid\ \longrightarrow\
\sum\limits_{i=l}^{r}a_i\geq mid(r-l+1)\ \longrightarrow\
\sum\limits_{i=l}^{r}a_i-mid(r-l+1)\geq 0\ \longrightarrow\
\sum\limits_{i=l}^{r}(a_i-mid)\geq 0
\]
此时，这是一个以 \(r\) 结尾的后缀和，可以直接 \(O(n)\) 地解决 .
这里还有一个问题，就是在我写的时候，发现比如说 \(0.755\) 不管是 printf(".3f") 还是 fixed setprecision 都不会进位到 \(0.76\) ，但是对于 \(0.7555\) 就会，我感到很迷惑.
时间复杂度 : \(O(n\log 10000a_i)\)
空间复杂度 : \(O(n)\)
#include<bits/stdc++.h>
using namespace std;
const long long inf=1e18+10;
int n,k;
long long a[300010],sum[300010];
inline int read(){
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)ch=getchar();
int res=0;
while(ch>=‘0‘&&ch<=‘9‘){
res=res*10+ch-‘0‘;
ch=getchar();
}
return res;
}
bool check(long long x){
for(int i=0;i<n;i++)sum[i]=a[i]-x;
for(int i=1;i<n;i++)sum[i]+=sum[i-1];
long long mx=-inf;
for(int i=0;i<n;i++){
if(mx!=-inf)mx+=a[i]-x;
if(i+1>=k)mx=max(mx,sum[i]-(i-k>=0?sum[i-k]:0));
if(mx>=0)return true;
}
return false;
}
int main(){
// freopen("test.txt","r",stdin);
n=read();k=read();
for(int i=0;i<n;i++)a[i]=read();
for(int i=0;i<n;i++)a[i]*=10000ll;
long long mx=a[0];
for(int i=1;i<n;i++)mx=max(mx,a[i]);
long long low=0,high=mx+1,ans=0;
while(low<high){
long long mid=(low+high)>>1;
if(check(mid)){
ans=max(ans,mid);
low=mid+1;
}
else{
high=mid;
}
}
printf("%lld",ans/10000);
int tmp=ans%10,res=ans%10000/10;
if(tmp%10>=5)res++;
printf(".");
vector<int>v;
for(int i=0;i<3;i++){
v.push_back(res%10);
res/=10;
}
for(int i=2;i>=0;i--)printf("%d",v[i]);
printf("\n");
return 0;
}
/*inline? ll or int? size? min max?*/