首页 > 代码库 > [51nod]1001 数组中和等于K的数对

[51nod]1001 数组中和等于K的数对

给出一个整数K和一个无序数组A,A的元素为N个互不相同的整数,找出数组A中所有和等于K的数对。例如K = 8,数组A:{-1,6,5,3,4,2,9,0,8},所有和等于8的数对包括(-1,9),(0,8),(2,6),(3,5)。
 
Input
第1行:用空格隔开的2个数,K N,N为A数组的长度。(2 <= N <= 50000,-10^9 <= K <= 10^9)
第2 - N + 1行:A数组的N个元素。(-10^9 <= A[i] <= 10^9) 
Output
第1 - M行:每行2个数,要求较小的数在前面,并且这M个数对按照较小的数升序排列。
如果不存在任何一组解则输出:No Solution。
Input示例
8 9
-1
6
5
3
4
2
9
0
8
Output示例
-1 9
0 8
2 6
3 5

一种是先排序,从头查找,二分查找K-a[i]是否在序列里。
第二种是逐步在两头寻找,逐步缩小范围,下一个数的范围一定在上一个之内
代码:
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn =  50000+10;
int a[maxn];
int N, K;

int cmp(int a, int b)
{
    return a > b;
}

bool IsFound(int x) 
{
    int l = 0, r = N-1, mid;
    while (l <= r) {
        mid = (l+r)>>1;
        if (a[mid] > x)
            r = mid -1;
        else if (a[mid] < x)
            l = mid + 1;
        else 
            return 1;
    }
    return 0;
}

int main()
{
    //freopen("1.txt", "r", stdin);
    scanf("%d%d", &K, &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+N);


    int flag = 0;
    for (int i = 0; i < N; i++) {
        if (IsFound(K-a[i]) && a[i]<K/2) {
            flag = 1;
            printf("%d %d\n", a[i], K-a[i]);
        }
    }
    
    if (!flag) printf("No Solution\n");


    return 0;
}
//
int flag = 0;
int j = N-1;
for (int i = 0; i < j; i++) {
    while (i < j && a[i]+a[j]>K) j--;  //缩小范围 
    if (a[i]+a[j] == k && i < j) {
        printf("%d %d\n", a[i], a[j]);
        flag = 1;
    }
}
if (!flag) printf("No solution\n");

 

 

[51nod]1001 数组中和等于K的数对