> #include<stdio.h> 
> #include<string.h> 
> #define MaxN 201 
> 
> int m,n,r,c; 
> double mar[MaxN][MaxN]; 
> double map[MaxN]; 
> int x1,y1,x2,y2; 
> int xx1,yy1,xx2,yy2; 
> double tmp,max; 
> 
> int init() 
> { int i,j; 
>  memset(mar,0,sizeof(mar)); 
>  scanf("%d",&m); if (m==0) return 0; 
>  scanf("%d %d %d",&n,&r,&c); 
>  for (i=1; i<=m; i++) 
>   for (j=1; j<=n; j++) 
>    {scanf("%lf",&mar[i][j]); mar[i][j]+=mar[i-1][j];} 
>  return 1; 
> } 
> 
> void save() 
> {max=tmp/(y2-y1+1); 
>  xx1=x1; yy1=y1; xx2=x2; yy2=y2; 
> } 
> 
> void check() 
> {if (tmp/(y2-y1+1)>max) 
>   save(); 
>  else if (tmp/(y2-y1+1)==max) 
>   {if (x1<xx1) 
>     save(); 
>    else if (x1==xx1&&y1<yy1) 
>     save(); 
>    else if (x1==xx1&&y1==yy1&&x2<xx2) 
>     save(); 
>    else if (x1==xx1&&y1==yy1&&x2==xx2&&y2<yy2) 
>     save(); 
>   } 
> } 
> 
> void minmap() 
> { int i; 
>  for (map[0]=0,i=1; i<=n; i++) map[i]=map[i-1]+map[i]; 
>  tmp=map[c]; y1=1; y2=c; check(); 
>  for (i=c+1; i<=n; i++) 
>   {if ((tmp+map[i]-map[i-1])/(y2-y1+1+1)>=(map[i]-map[i-c])/c) 
>     {tmp=tmp+map[i]-map[i-1]; y2++;} 
>    else 
>     {tmp=(map[i]-map[i-c]); y2++; y1=y2-c+1;} 
>    check(); 
>   } 
> } 
> 
> void search() 
> { int i; 
>  max=-1; xx1=-1; yy1=-1; xx2=-1; yy2=-1; 
>  for (x1=1; x1<=m; x1++) 
>   for (x2=x1+r-1; x2<=m; x2++) 
>    {for (i=1; i<=n; i++) map[i]=(mar[x2][i]-mar[x1-1][i])/(x2-x1+1); 
>     minmap(); 
>    } 
>  printf("%d %d %d %d\n",xx1,yy1,xx2,yy2); 
> } 
> 
> int main() 
> {while (init()) 
>   search(); 
>  printf("*\n"); 
>  return 0; 
> }

• 我的答案比你的优，而且相差1以上，应该不是精度问题，你的算法估计是有问题的 (0) dynamic 2003-11-04 18:27:25
  • 不过你的算法也是很接近最优解的，而且100组只相差了5组。官方数据好像只有3组，太弱了 (0) dynamic 2003-11-04 18:32:05
• 把你随机出来的数据发给我吧,我加上去 (18) hawk 2003-11-04 18:48:02
  • done,数据虽然有100组，但宽都是1，也就是说不是卡速度的，如果想卡速度的话要随机一些大数据:) (22) dynamic 2003-11-04 18:58:15