0

我遇到了一个帖子找到两个数组之间的最小差异
并使用我试图解决 SPOJ 问题的概念 - http://www.spoj.pl/problems/ACPC11B 但奇怪的是我得到了 WA（错误答案）！！！ ！

然后我尝试了简单的方法..
使用两个for循环..
计算每个元素之间的差异......
然后我得到了AC。！！！！

谁能告诉我为什么这种方法
if (|A[i+1] - B[j]| < |A[i] - B[j+1]|) 然后递增 i，否则在这种情况下递增 j 失败？ ？？？

编辑：我忘了提到，当我实现第一种方法时，我已经对两个数组执行了 qsort ......
同样在 SPOJ 问题中，不需要差异最小的元素的索引。只需要最小差异！

4

3 回答 3

2

第一个链接中的方法仅在两个数组都已排序时才有效。SPOJ 问题涉及未排序的数组。这就是为什么该方法不起作用的原因。如果您对数组进行排序，您可以应用第一种方法，但是您需要跟踪原始索引（即排序前每个值的位置）。这可以通过将每个值转换为 (value, index) 对然后对这些对进行排序来实现。这样，您将获得 O(m log m + n log n) 解决方案，而不是蛮力（但正确） O(mn) 解决方案（其中 m 和 n 是数组长度）。

编辑根据您发布的代码，我有不同的答案。你的循环条件是错误的。例如， if i == (x - 1)but j != (y - 1)，循环将执行，您将a[x]与b[j]. 这是 的非法下标a。此外，这是否应该读取与 SPOJ 中描述的相同的输入？我看不到您在哪里阅读测试用例的数量。

于 2012-05-23T19:35:50.360 回答
0

您不会比较数组的第一个元素。也就是说，如果最小差是 | a[0]-b[0]| 并且在任何其他元素对之间不会出现这种差异，您不会发现它，因为您的比较以 | 开头 a[1]-b[0]| 和 | a[0]-b[1]|。

于 2012-05-24T10:04:23.717 回答
0

这就是我认为应该做的事情（基于你的代码），基本上你的代码没有检查2个案例：

首先，当最小值介于数组中的第一个值之间时。

第二个是我们检查了一个数组中的每个值，但第二个数组中仍然有值。（考虑情况 a[0,1,2], b[-1,-2,-3,-5,-6,2]）

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


int comp(const void * a,const void * b)
{
    if (*(int*)a==*(int*)b)
        return 0;
    else if (*(int*)a < *(int*)b)
        return -1;
    else
        return 1;
}

int main()
{
    int x,y;
    printf("x: ");
    scanf ("%d", &x);
    int a[x];
    srand(time(NULL));
    for (int i = 0; i < x; i++)
    {
        a[i] = rand() % 30 - 15;
        //scanf ("%d", &a[i]);
        printf ("%d\n",a[i]);
    }

    printf("y: ");
    scanf ("%d", &y);

    int b[y];
    for (int i = 0; i < y; i++)
    {
        b[i] = rand() % 30 - 15;
        //scanf ("%d", &b[i]);
        printf ("%d\n",b[i]);
    }


    qsort(a,x,sizeof(int),comp) ;
    qsort(b,y,sizeof(int),comp) ;
    int i = 0, j = 0;
    int * inc; // using a pointer to select which var to increment. Avoid repeating code, optional and subjective approach.
    int minimum = abs(a[0]-b[0]); // Set min to be a[0] - b[0] which is never checked in the loop

    /* Added the min > 0 condition to avoid looping unnecessarily and avoid the break statement
    Changed the condition from && to || in order to handle the second case
    Changed the != to < which is more restrictive */
    while (minimum > 0 && (i < (x - 1) || j < (y - 1)))
    {

        int z;
        if ( i == x-1) // we've reached the end of a, inc j automatically
        {
            inc = &j;
            z = abs(a[i]-b[j+1]);
        }
        else if ( j == y -1 ) // we've reached the end of b, inc i automatically
        {
            inc = &i;
            z = abs(a[i+1]-b[j]);
        }
        else // here's the original loop, rewritten to shorten the code
        {
            int zi = abs(a[i+1]-b[j]);
            int zj = abs(a[i]-b[j+1]);
            if ( zi < zj)
            {
                inc = &i;
                z = zi;
            }
            else
            {
                inc = &j;
                z = zj;
            }
        }
        if ( z < minimum)
        {
            minimum = z;
        }

        (*inc)++;
    }
    printf("min: ");
    printf ("%d\n", minimum);
    return 0;

}
于 2012-05-24T11:46:29.197 回答