51Nod－1001－數組中和等于K的數對

ACM模版

描述

題解

這道題兩種辦法解，兩種辦法的通性是都需要排序，但是資料結構截然不同。

第一種辦法是源資料進行從小到大排序，然後定一個哨兵

flag

，來卡住查找的範圍，以此來達到減少查找次數。

第二種辦法比較巧，将複雜度為O(n*m)降低為O(n)。效率略微提高，使用的手段是将資料結構改造了一下，給源資料捆綁了一個

antival

的輔助資料。當

a[i].val < k / 2

時，

a[i].antival = a[i].val

反之等于

k - a[i].val

,然後根據

antival

作為主鍵進行排序，查找時，直接查找相鄰的兩項

antival

相等的結果，這裡需要說明的是，因為題意上說每個資料都互不相同，是以相等的兩個

antival

對應的

val

一定是相加等于K。

代碼

One：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN =  + ;

int A[MAXN];

int main(int argc, const char * argv[])
{
    freopen("input.txt", "r", stdin);
    int K, N;
    while (cin >> K >> N)
    {
        bool tag = false;
        for (int i = ; i < N; i++)
        {
            scanf("%d", A + i);
        }
        sort(A, A + N);
        int B;
        int flag = N;
        for (int i = ; i < N - ; i++)
        {
            B = K - A[i];
            for (int j = flag - ; j > i; j--)
            {
                if (B == A[j])
                {
                    printf("%d %d\n", A[i], B);
                    flag = j;
                    tag = true;
                    break;
                }
                else if (B > A[j])
                {
                    flag = j + ;
                    break;
                }
            }
        }
        if (!tag)
        {
            puts("No Solution");
        }
    }

    return ;
}
           

Two：

#include <cstdio>
#include <algorithm>

using namespace std;

#define maxn 50010

struct node
{
    int val, antival;
} a[maxn];

int cmp(node x, node y)
{
    if (x.antival == y.antival)
    {
        return x.val < y.val;
    }
    return x.antival < y.antival;
}

int main()
{
    int n, i, k;
    while (scanf("%d%d", &k, &n) != EOF)
    {
        for (i = ; i < n; ++i)
        {
            scanf("%d", &a[i].val);
            if (a[i].val < k/)
            {
                a[i].antival = a[i].val;
            }
            else
            {
                a[i].antival = k - a[i].val;
            }
        }
        sort(a, a + n, cmp);
        bool sign = false;
        for (i = ; i < n - ; ++i)
        {
            if (a[i].antival == a[i + ].antival)
            {
                printf("%d %d\n", a[i].val, a[i + ].val);
                sign = true;
            }
        }
        if (!sign)
        {
            printf("No Solution\n");
        }
    }
    return ;
}