[已解决]C语言 最近对问题

William_Prince

下面是题目和测试用例


以下是我的代码

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. #include <string.h>
   
5. 
   
6. #define INF 2147483647
   
7. #define N 1000000
   
8. 
   
9. struct node{
   
10.         int x;
    
11.         int y;
    
12. }point[N];
    
13. 
    
14. int cmp(const void *a,const void *b)
    
15. {
    
16.         struct node ac = *(struct node*)a;
    
17.         struct node bd = *(struct node*)b;
    
18.         if (ac.x != bd.x)
    
19.                 return ac.x - bd.x;
    
20.         else return ac.y - bd.y;
    
21. }//结构体排序
    
22. 
    
23. 
    
24. int mindistance(int left,int right){
    
25.         return left<right?left:right;//返回大小关系
    
26. }
    
27. 
    
28. int distance(int left,int right){
    
29.         return ((point[left].x - point[right].x)*(point[left].x - point[right].x) + (point[left].y - point[right].y)*(point[left].y - point[right].y));
    
30. }//计算距离的平方
    
31. 
    
32. int Closest_Pair(int left,int right){
    
33.         int End_dis = INF;
    
34.         int i=0,j=0,k=0;
    
35.        
    
36.         if (left == right) return End_dis;//假如区间里面只有一个点，那么返回无穷大
    
37.         if (right - left == 1) return distance(left,right);//假如区间里面只有两个点，那么直接返回这两点之间距离的平方
    
38.          
    
39.        
    
40.         int mid = (left + right)/2;//计算中线，判断是否是大于等于三个点的情况
    
41.        
    
42.         int distanceleft  = Closest_Pair(left,mid);//左边递归
    
43.         int distanceright = Closest_Pair(mid+1,right);//右边递归
    
44.        
    
45.         End_dis = mindistance(distanceleft,distanceright) ;//比较左右两边距离的平方，找出最小值，即为d
    
46.        
    
47.         int temp[N] = {0}; //储存宽度为d的点
    
48.        
    
49.         for (i = left; i < right; i++){//找出符合要求的距离mid横坐标的平方小于d的点
    
50.                 if ( (point[left].x - point[right].x)*(point[left].x - point[right].x) <= End_dis ){
    
51.                         temp[k++] = i;//temp用来暂时存储符合要求的点的序号
    
52.                 }
    
53.         }
    
54.         for (i=0; i<k; i++){
    
55.                 for(j=i+1; j<k&&j<i+7; j++){
    
56.                         if ((point[temp[i]].y - point[temp[j]].y)*(point[temp[i]].y - point[temp[j]].y) <End_dis)
    
57.                                 End_dis = mindistance(End_dis,distance(temp[i],temp[j]));
    
58.                 }
    
59.         }
    
60.         return End_dis;       
    
61. }
    
62. 
    
63. int main(){
    
64.         int n,i;
    
65.         scanf("%d",&n);
    
66.         for(i=0;i<n;i++){
    
67.                 scanf ("%d %d",&point[i].x,&point[i].y);
    
68.         }
    
69.         qsort(point,n,sizeof(point[0]),cmp);
    
70.         printf("%d\n",Closest_Pair(0,n-1));
    
71.         return 0;
    
72. }

复制代码

这个代码第一个测试用例就过不去，我想请问一下问题出在哪里
同时，假如我把数组开到10^6，不管我输入什么，都会出现下图问题

想请教一下大家问题出在哪里，谢谢！

最佳答案

月排行榜 / 总排行榜

jhq999

2021-10-31 01:11:04

静态数组定义的太大了。

1. int Closest_Pair(int left,int right){
   
2.         int End_dis = INF;
   
3.         int i=0,j=0,k=0;
   
4.         
   
5.         if (left == right) return End_dis;//假如区间里面只有一个点，那么返回无穷大
   
6.         if (right - left == 1) return distance(left,right);//假如区间里面只有两个点，那么直接返回这两点之间距离的平方
   
7.          
   
8.         
   
9.         int mid = (left + right)/2;//计算中线，判断是否是大于等于三个点的情况
   
10.         
    
11.         int distanceleft  = Closest_Pair(left,mid);//左边递归
    
12.         int distanceright = Closest_Pair(mid+1,right);//右边递归
    
13.         
    
14.         End_dis = mindistance(distanceleft,distanceright) ;//比较左右两边距离的平方，找出最小值，即为d
    
15.         //////////
    
16.         int *temp = new int[N]; //储存宽度为d的点
    
17.         //////////
    
18.         for (i = left; i < right; i++){//找出符合要求的距离mid横坐标的平方小于d的点
    
19.                 if ( (point[left].x - point[right].x)*(point[left].x - point[right].x) <= End_dis ){
    
20.                         temp[k++] = i;//temp用来暂时存储符合要求的点的序号
    
21.                 }
    
22.         }
    
23.         for (i=0; i<k; i++){
    
24.                 for(j=i+1; j<k&&j<i+7; j++){
    
25.                         if ((point[temp[i]].y - point[temp[j]].y)*(point[temp[i]].y - point[temp[j]].y) <End_dis)
    
26.                                 End_dis = mindistance(End_dis,distance(temp[i],temp[j]));
    
27.                 }
    
28.         }
    
29.                 delete[] temp;////////////
    
30.         return End_dis;        
    
31. }

复制代码

跳转到最佳答案楼层

jhq999

静态数组定义的太大了。

1. int Closest_Pair(int left,int right){
   
2.         int End_dis = INF;
   
3.         int i=0,j=0,k=0;
   
4.         
   
5.         if (left == right) return End_dis;//假如区间里面只有一个点，那么返回无穷大
   
6.         if (right - left == 1) return distance(left,right);//假如区间里面只有两个点，那么直接返回这两点之间距离的平方
   
7.          
   
8.         
   
9.         int mid = (left + right)/2;//计算中线，判断是否是大于等于三个点的情况
   
10.         
    
11.         int distanceleft  = Closest_Pair(left,mid);//左边递归
    
12.         int distanceright = Closest_Pair(mid+1,right);//右边递归
    
13.         
    
14.         End_dis = mindistance(distanceleft,distanceright) ;//比较左右两边距离的平方，找出最小值，即为d
    
15.         //////////
    
16.         int *temp = new int[N]; //储存宽度为d的点
    
17.         //////////
    
18.         for (i = left; i < right; i++){//找出符合要求的距离mid横坐标的平方小于d的点
    
19.                 if ( (point[left].x - point[right].x)*(point[left].x - point[right].x) <= End_dis ){
    
20.                         temp[k++] = i;//temp用来暂时存储符合要求的点的序号
    
21.                 }
    
22.         }
    
23.         for (i=0; i<k; i++){
    
24.                 for(j=i+1; j<k&&j<i+7; j++){
    
25.                         if ((point[temp[i]].y - point[temp[j]].y)*(point[temp[i]].y - point[temp[j]].y) <End_dis)
    
26.                                 End_dis = mindistance(End_dis,distance(temp[i],temp[j]));
    
27.                 }
    
28.         }
    
29.                 delete[] temp;////////////
    
30.         return End_dis;        
    
31. }

复制代码

傻眼貓咪

n 不超过 1000000
x、y不超过 10000
以你的代码时间复杂度，不超时（TLE）吗？

William_Prince

jhq999 发表于 2021-10-31 01:11
静态数组定义的太大了。

谢谢！这段改完之后还是有一个超时，然后我把数组开到全局变量里头就过了。