我正在CodeChef上解决问题。问题链接是这样的::http://www.codechef.com/problems/POINTS
在问题中,我们将2D平面中的坐标作为用户的输入,然后从具有最小x坐标和最大y坐标的点移动到最大x坐标和最小y坐标,然后计算距离旅行。
我打算做的是,从用户那里获取所有点的输入,然后使用在x和y坐标上给出的条件对它们进行排序。
这是我的代码::
#include<stdio.h>
int x[100000][2];//coordinates
int c[100000][2];
void sort(int a[][2], int low, int high); //sorting the points
void merge(int a[][2],int low, int mid,int high); //merge sort
int main()
{
int t;//number of test cases
int n;//number of points
int i;
scanf("%d",&t);
while(t--)
{
printf("\n");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d %d",&x[i][0],&x[i][1]);
sort(x,0,n-1);
for(i=0;i<n;i++)
printf("%d %d\n", x[i][0],x[i][1]);
}
return 0;
}
void sort(int a[][2], int low, int high)
{
int mid;
while(low<high)
{
mid=(low+high)/2;
sort(a,low,mid);
sort(a,mid+1,high);
merge(a,low,mid,high);
}
}
void merge(int a[][2],int low, int mid,int high)
{
int i=low, j=mid+1;
int k=low;
while(i<=mid && j<=high)
{
if(a[i][0]<a[j][0])
{
c[k][0]=a[i][0];
c[k][1]=a[i][1];
i++;k++;
}
else if(a[i][0]>a[j][0])
{
c[k][0]=a[j][0];
c[k][1]=a[j][1];
j++;k++;
}
else
{
if(a[i][1]>a[j][1])
{
c[k][0]=a[i][0];
c[k][1]=a[i][1];
i++;k++;
}
else
{
c[k][0]=a[j][0];
c[k][1]=a[j][1];
j++;k++;
}
}
}
for(i=low;i<=high;i++)
{
a[i][0]=c[i][0];
a[i][1]=c[i][1];
}
}
我以为数组太大了,这就是导致运行时错误的原因,所以我尝试将数组大小减小到100,然后运行程序,但是仍然会导致运行时错误。现在,在我发布的代码中,我只希望对坐标进行排序。排序条件是这样的::(如问题所给)
您从X值和Y值最小的点开始,到X值和Y值最小的点结束。移动的规则是,您不能移动到X值小于所在点的X值的点。同样,对于具有相同X值的点,您需要先访问具有最大Y值的点,然后再访问具有相同X值的下一个点。因此,如果有2个点:(0,4和4,0),我们将从(0,4)开始-即,最小的X优先于最大的Y。您需要访问飞机上的每个点。
好的,我认为我已经确定了问题所在:
sort()
,替换while
为if
。那里没有循环的原因-您可以通过递归来实现merge()
不正确。如果其中一个i
或j
超出范围,则其他合并片的其余部分不会合并到中c
。我建议迭代遍历k
,因为无论如何您都需要遍历整个目标范围。请注意,当遍历k
您需要检查i
或者j
是出界-如果是这样,您只需在要素从其他片复制。我使用短路评估来执行此操作,也就是说,边界检查语句位于运算符之前||
,这很重要,否则可能会访问无效的内存!(如有需要,请随时要求进一步的解释)这是应用以上修复程序后的代码:
void sort(int a[][2], int low, int high)
{
int mid;
if(low < high)
{
mid=(low+high)/2;
sort(a,low,mid);
sort(a,mid+1,high);
merge(a,low,mid,high);
}
}
void merge(int a[][2],int low, int mid, int high)
{
int i = low,
j = mid + 1,
k = low;
for (k = low; k <= high; k++)
{
if((j > high) || (a[i][0] < a[j][0]))
{
c[k][0]=a[i][0];
c[k][1]=a[i][1];
i++;
}
else if((i > mid) || (a[i][0] > a[j][0]))
{
c[k][0]=a[j][0];
c[k][1]=a[j][1];
j++;
}
else // Neither i nor j are out of bounds and the 0 element is equal
{
if(a[i][1] > a[j][1])
{
c[k][0] = a[i][0];
c[k][1] = a[i][1];
i++;
}
else
{
c[k][0] = a[j][0];
c[k][1] = a[j][1];
j++;
}
}
}
for(i = low; i <= high; i++)
{
a[i][0] = c[i][0];
a[i][1] = c[i][1];
}
}
我相信上面的代码可以满足您的需求。
一些一般性建议:您可能想使用一个简单的结构来存储坐标。该代码将变得更易于阅读-易于阅读的代码也易于调试。同样,如果可能,一般应避免使用全局变量。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句