0

私は投稿に出くわしました2つの配列間の最小差を見つけ、
概念を使用してSPOJの問題を解決しようとしました- http://www.spoj.pl/problems/ACPC11B しかし、不思議なことに、私はWA（間違った答え）を得ました!!! !

次に、簡単な方法を試しました..
2 つの for ループを使用して..
各要素とすべての要素の差を計算すると、
AC が得られました。!!!!


(|A[i+1] - B[j]| < |A[i] - B[j+1]|) の場合、このメソッドが i をインクリメントする理由を誰か教えてください。 ???

編集:最初のメソッドを実装したときに、両方の配列で既に qsort を実行したことを忘れていました...
SPOJ の質問でも、差が最小である要素のインデックスは必要ありません。最低限の違いだけが必要です!!!

4

3 に答える 3

2

最初のリンクの方法は、両方の配列がソートされている場合にのみ機能します。SPOJ の問題には、並べ替えられていない配列が含まれます。そのため、この方法は機能しませんでした。配列を並べ替える場合、最初の方法を適用できますが、元のインデックス (つまり、並べ替える前の各値の位置) を追跡する必要があります。これは、各値を (値、インデックス) ペアに変換し、ペアを並べ替えることで実行できます。そうすれば、ブルートフォース（ただし正しい）O（mn）ソリューション（mとnは配列の長さ）の代わりに、O（m log m + n log n）ソリューションが得られます。

編集投稿されたコードに基づいて、別の答えがあります。ループ条件が間違っています。たとえば、i == (x - 1)butj != (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つのケースをチェックしませんでした：

最初は、最小値が配列内の最初の 2 つの値の間にある場合です。

2 つ目は、1 つの配列のすべての値をチェックしたが、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 に答える