就比如这组数据
79
27 42
-22 -10 -15 48 -51 -12 -60 -17 -35 -15 24 22 -21 -20 -55 14 -68 -3 12 -13 27 -17 16 -52 -76 -26 8 -23 40 -28 4 -74 -6 41 11 53 13 -49 -54 66 -56 -36 -58 39 11 -65 23 -58 -42 -63 13 1 41 -75 35 45 56 -71 78 -30 -41 -7 -64 -63 78 37 -53 19 54 44 79 -20 -70 67 79 -41 33 35 12
到底是9.518还是9.519啊qaq
by Loi_Anina @ 2018-10-24 09:15:34
@[Loi_Anina](/space/show?uid=69864) printf("%.3lf",ans);
by 小可爱三岁七 @ 2018-10-24 09:28:28
楼上正解(
by Dirt、 @ 2018-10-24 09:30:33
@[小可爱三岁七](/space/show?uid=62490)
!??我是这么输出的啊QAQ
by Loi_Anina @ 2018-10-24 09:33:20
@[Dirt、](/space/show?uid=91889) 你现在不应该在认真学习?
by Loi_Anina @ 2018-10-24 09:33:36
@[Loi_Anina](/space/show?uid=69864) ~~讲的树剖什么的听不懂~~
by Dirt、 @ 2018-10-24 09:40:01
@[Loi_Anina](/space/show?uid=69864)
和答案最后一位相差比较大啊……应该不大是精度问题……您能放一下代码吗?
by 小可爱三岁七 @ 2018-10-24 09:44:21
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#define Inf 1e9
using namespace std;
int n;
int S,T;
int a[100010];
long long int f[100010];
int l=Inf,r=-Inf;
int mid;
struct number
{
int num,pos;
}qvq[100010];
int check(int x)
{
memset(f,0,sizeof(f));
memset(qvq,0,sizeof(qvq));
for(int i=1;i<=n;i++) f[i]=f[i-1]+a[i]-x;
int head=1,tail=0;
for(int i=S;i<=n;i++)
{
while(qvq[tail].num>f[i-S]&&head<=tail) tail--;
qvq[++tail].num=f[i-S],qvq[tail].pos=i-S;
while(head<=tail&&qvq[head].pos<i-T) head++;
if(head<=tail&&f[i]-qvq[head].num>=0) return 1;
}
return 0;
}
int res;
int las;
double op;
int main()
{
// freopen("rand.in","r",stdin);
// freopen("data.ans","w",stdout);
scanf("%d",&n);
scanf("%d%d",&S,&T);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]=a[i]*1000;
r=max(r,a[i]);
l=min(l,a[i]);
}
while(l<=r)
{
// cout<<mid<<" ";
mid=(l+r)>>1;
if(check(mid))//可以再大
{
l=mid+1;
res=mid;
}
else//必须减小
{
r=mid-1;
}
}
// cout<<res<<" ";
printf("%.3lf",(double)res/1000);
return 0;
}
/*
12
6 8
10 7 -7 10 5 9 2 -4 0 8 -7 -2
*/
```
我也感觉不只是精度问题Orz,但是看题解我的思路和写法感觉基本都是对的Orz
by Loi_Anina @ 2018-10-24 09:51:34
@[Loi_Anina](/space/show?uid=69864) 不清楚哎……你可以试试扩大的倍数大一点。
by 小可爱三岁七 @ 2018-10-24 10:01:24
@[Loi_Anina](/space/show?uid=69864) 1000可能有精度问题的。
by 小可爱三岁七 @ 2018-10-24 10:01:43