代码练习生 @ 2020-07-16 16:09:41
这究竟是为什么???
#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;
}
by gongyr @ 2020-07-16 16:11:25
和谁对比???
by Stamford_Bridge @ 2020-07-16 16:13:35
@gongyr 难道是题解(逃
by 代码练习生 @ 2020-07-16 16:23:53
@gongyr 题解呗,,,
by yummy @ 2020-07-16 16:25:04
@代码练习生 天哪这里面有些语法我见都没见过
建议楼主不要使用C++11及以上新特性
by yummy @ 2020-07-16 16:25:25
唉不是C++11及以上啊
by 代码练习生 @ 2020-07-16 16:25:28
@yummy 这是c啊,,,
by 代码练习生 @ 2020-07-16 16:26:06
@gongyr 终于对了,,, 在我把l+=1,r+=1 改为 l+=100,r+=200之后,,,, 看到很多r+=2我都已经无法理解了,,, 为什么我这个还得加这么多,,, 玄学问题吗,,,