精度问题求助
  • 板块P1419 寻找段落
  • 楼主bugfix
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/9/13 02:35
  • 上次更新2023/11/5 13:18:07
查看原帖
精度问题求助
372789
bugfix楼主2020/9/13 02:35
#include<stdio.h>
#define MAXN 100001
#define eps 1e-3

int n,S,T,arr[MAXN],q[MAXN];
double sum[MAXN];

int check(double m){
    sum[0]=arr[0]-m;
    int i=1;
    while(i<n){
        sum[i]=sum[i-1]+arr[i]-m;
        ++i;
    }
    int head=0,tail=-1;
  
    int offset=S,t;

  i=offset;
while(i<=T){
if(sum[i-1]>=0)return 1;
++i;
}
i=offset;
    while(i<n){
        t = i-offset;
        while(head<=tail&&sum[t]<sum[q[tail]])--tail;
        q[++tail]=t;
        while(head<=tail&&i-q[head]>T)++head;
        if(head<=tail&&sum[i]-sum[q[head]]>=0)return 1;
        ++i;
    }
    return 0;
}

int main(){
    scanf("%d%d%d",&n,&S,&T);
    int i=0;
    while(i<n)scanf("%d",&arr[i++]);
    double l=-10000.0,r=10000.0,m;
    while(r-l>=eps){
        m = (l+r)/2;
        if(check(m))l=m;
        else r=m;
    }
    printf("%.3f\n",l);
    return 0;
}

不是精确到小数点后三位吗,当r-l大于等于1e-3时,就继续循环,直到r-l小于1e-3,说明r和l的差别已经比0.001还要小,就可以打印答案了,为啥还是WA了几个点呢?求解答

2020/9/13 02:35
加载中...