心态崩了,比对了一个多小时了,老有两个不对,完全不知道哪里错了
查看原帖
心态崩了,比对了一个多小时了,老有两个不对,完全不知道哪里错了
340222
代码练习生楼主2020/7/16 16:09

这究竟是为什么???

#include<stdio.h>
#include<stdlib.h>

void
constructQZH(int ** stones,int ** QZH,int n,int bz){
    int i;
    
    for(i=1;i<=n;i++){
        QZH[0][i]=QZH[0][i-1];
        QZH[1][i]=QZH[1][i-1];
        if(stones[0][i]>=bz){
            QZH[0][i]+=1;
            QZH[1][i]+=stones[1][i];
        }
    }
}

long
getY(int ** ranges,int m,int ** QZH){
    int i;
    long sum=0;
    
    for(i=0;i<m;i++){
        sum+=(QZH[0][ranges[1][i]]-QZH[0][ranges[0][i]-1])*(QZH[1][ranges[1][i]]-QZH[1][ranges[0][i]-1]);
    }
    return sum;
}

int
main(){
    int n,m,*stones[2],*ranges[2],*QZH[2],l,r,mid;
    long min,s,y;
    
    scanf("%d %d %ld",&n,&m,&s);
    stones[0]=malloc(sizeof(int)*(n+1));
    ranges[0]=malloc(sizeof(int)*m);
    QZH[0]=malloc(sizeof(int)*(n+1));
    stones[1]=malloc(sizeof(int)*(n+1));
    ranges[1]=malloc(sizeof(int)*m);
    QZH[1]=malloc(sizeof(int)*(n+1));
    min=(unsigned long)(-1)/2;
    
    stones[0][0]=stones[1][0]=QZH[0][0]=QZH[1][0]=0;
    scanf(" %d %d",stones[0]+1,stones[1]+1);
    l=r=stones[0][1];
    for(mid=2;mid<=n;mid++){
        scanf(" %d %d",stones[0]+mid,stones[1]+mid);
        if(stones[0][mid]<l)
            l=stones[0][mid];
        else if(stones[0][mid]>r)
            r=stones[0][mid];
    }
    for(mid=0;mid<m;mid++){
        scanf(" %d %d",ranges[0]+mid,ranges[1]+mid);
    }
    l-=1;
    r+=2; 
    while(l<=r){                
    /*
    千万要注意是l<=r,而不是l<r,
    大有区别,会漏掉一个,这和前面那两个二分题是不一样的,
    他们保留了mid,若是用l<=r的话就会陷入死循环。
    */
        mid=(l+r)>>1;
        constructQZH(stones,QZH,n,mid);
        y=getY(ranges,m,QZH);
        if(s<y)
            l=mid+1;          //说明条件太放松了,要加强
        else if(s==y){
            min=0;
            break;
        }else{
            r=mid-1;        //条件太苛刻,要放松,跟前两题不同,我们有了min来保存,故不指望回到mid。
        }
        y=y<s?(s-y):(y-s);
        min=min<y?min:y;
    }
    printf("%ld",min);
    return 0;
}
2020/7/16 16:09
加载中...