社区讨论
不解:为什么需要二分?(全wa)
P1419寻找段落参与者 3已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @m1sxnxy1
- 此快照首次捕获于
- 2024/10/03 14:46 去年
- 此快照最后确认于
- 2025/11/04 18:13 4 个月前
rt,既然维护单调队列就可以求出平均值,区间长度范围已知,为什么需要二分呢?(本蒟蒻可能对二分与单调理解不佳)
CPP#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,S,T;
double sum=0,ans=-1e9;
int a[N],b[N],l=0,r=0 ;
int q[N] ;
int main()
{
scanf("%d%d%d",&n,&S,&T) ;
for(int i=1 ;i<=n ;++i)
{
scanf("%d",&a[i]) ;
b[i]=a[i]+b[i-1] ;
}
for(int i=S,j=0 ;i<=n ;++i,++j)
{
while(l<=r&&(i-q[l])>T )
{
++l ;
}
while(l<=r&&b[j]<b[q[r]])
{
--r;
}
q[++r]=j;
ans=std::max(ans,(double)(b[i]-b[q[l]]) / (double)(i-q[l])) ;
}
printf("%.3f",ans) ;
}
ps:该代码全wa
回复
共 6 条回复,欢迎继续交流。
正在加载回复...