OJ 8207

Author Avatar
LittleBlack 1月 27, 2019
  • 在其它设备中阅读本文章

07:和为给定数

题目

  • 描述
    给出若干个整数,询问其中是否有一对数的和等于给定的数。

  • 输入
    共三行:
    第一行是整数n(0 < n <= 100,000),表示有n个整数。
    第二行是n个整数。整数的范围是在0到10^8之间。
    第三行是一个整数m(0 <= m <= 2^30),表示需要得到的和。

  • 输出
    若存在和为m的数对,输出两个整数,小的在前,大的在后,中间用单个空格隔开。若有多个数对满足条件,选择数对中较小的数更小的。若找不到符合要求的数对,输出一行No。
  • 样例输入
    4
    2 5 1 4
    6
  • 样例输出
    1 5

思路

  • 使用for循环枚举第一个加数i
  • 在for中嵌套while 二分查找符合的加数

代码

#include <bits/stdc++.h> //万能的头文件
using namespace std;

int main() {
    //输入
    int n;
    cin>>n;
    if(n<=1){    //小于等于1的数量构不成数对 
        cout<<"No";
        return 0;
    }
    long long arr[n],m;        //保险起见把数组和m都设为longlong 
    for(int i=0;i<n;i++) cin>>arr[i];
    cin>>m;
    //升序数组
    sort(arr,arr+n);    //升序排序,方便二分查找 
    //开始查找 
    for(int i=0;i<n;i++){ //第一个加数的循环 
        int l=i+1,r=n-1,mid=(l+r)/2;    //第二个加数 
        while(l<=r){    //l和r存在重合的情况 
            if(arr[i]+arr[mid]<m) l=mid+1;
            if(arr[i]+arr[mid]>m) r=mid-1;
            if(arr[i]+arr[mid]==m){    //当找到了的时候 
                cout<<arr[i]<<' '<<arr[mid];
                return 0;
            }
            mid=(l+r)/2;    //不要忘掉刷新mid 
        }
    } 
    //没找到
    cout<<"No"; 
    return 0;
}

总结

  1. 在确定第一个加数的情况下二分第二个加数
  2. 看请题目确认好long long 类型的m
  3. 考虑到边界情况:如果是0怎么办
  4. while的最后不要忘记刷新mid,不然死循环