51nod 1001_数组中和等于K的数对_二分

lzusa 发布于 2017-12-08 933 次阅读

题目描述

给出一个整数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)。

思路

枚举一个二分一个，很优秀。

 

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
#define N 50001
#define INF 0x7f7f7f7f
int a[N];
int n, k;
int cmp(int a, int b)
{
    return a < b;
}
int find(int lf, int rt, int x)
{
    int l = lf, r = rt;
    int m = (l + r) >> 1;
    if (a[m] == x) return 1;
    while (l < r)
    {
        if (a[l] > x || a[r] < x) return 0;
        if (a[m] > x) r = m - 1;
        else if (a[m] < x) l = m + 1;
        m = (l + r) >> 1;
        if (a[m] == x) return 1;
    }
    return 0;
}
int main()
{
    scanf("%d%d", &k, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1, cmp);
    bool fl = 0;
    for (int i = 1; i <= n; i++)
    {
        if (find(i + 1, n, k - a[i]))
        {
            printf("%d %d\n", a[i], k - a[i]);
            fl = 1;
        }
    }
    if (!fl) printf("No Solution\n");
}

 

]]>