2863: 【例56.1】 和为给定数

内存限制：64 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：5 解决：5

题目描述

现给出若干个整数，询问其中是否有一对数的和等于给定的数。

输入

共三行：
第一行是整数$n$($0 < n ≤ 100,000$)，表示有$n$个整数。
第二行是$n$个整数。整数的范围是在 $0$ 到$2×10^8$之间。
第三行是一个整数$m$($0≤m≤2^{30}$)，表示需要得到的和。

输出

若存在和为 $m$ 的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行"No"。

样例输入 复制 

4
2 5 1 4
6

样例输出 复制 

1 5

提示

其实在STL里面也有已经实现好的二分函数，包含于algorithm库中。
lower_bound(begin,end,val)：在有序数组[begin,end) 中找到第一个大于等于val的值并返回其地址。
upper_bound(begin,end,val)：在有序数组[begin,end)中找到第一个大于val的值并返回其地址。
和大多数STL 函数一样，begin指数组首地址，end指末地址+1。

lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。 


#include<bits/stdc++.h>
using namespace std;
int a [100005];
int main(){
    int n,x;
    int *b;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>x;
    sort(a,a+n);
    for(int i=0;i<n;i++){
        b=lower_bound(a,a+n,x-a[i]);
        if(b-a==i&&*(b+1)!=*b) continue;
        if(*b==x-a[i]){
            cout<<a[i]<<" "<<x-a[i];
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

来源/分类

提交提交记录统计露一手!