折腾笔记-计蒜客T1158-和为给定数AC记

欢迎查看原题

1.简单题目叙述

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

输入格式共三行：第一行是整数 $n(0 < n le 100,000)n(0<n≤100,000$ )$ )，表示有 n 个整数。

第二行是 n 个整数。整数的范围是在 0 到 $2 imes 10^8$ 之间。

第三行是一个整数 $m(0 le m le 2^{30})$ ，表示需要得到的和。

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

输出时每行末尾的多余空格，不影响答案正确性

样例输入

4
2 5 1 4
6

样例输出

1 5

初步思路：

爆搜，代码如下：

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    long long int a[666666];
    for(int i = 0;i<n;++i) {
        cin>>a[i];
    }
    int m;
    cin>>m;
    sort(a,a+n);
    for(int i = 0;i<n;++i) {
        long long tmp = m-i;
        for(int j = i;j<n;++j) {
            if(a[j]==tmp) {
                cout<<i<<" "<<a[j];
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
}

可惜搜的不对，50分。。。

经排查，原因如下：

i 现在表示的是第一个数，那应该从 0 到 $2 imes 10 ^ 8$ 都试，这不太行，可以看的是 a[i] 找 m - a[i] 这样就好了，不过需要考虑当一个数是 m / 2 的时候怎么找另一个数，比较好的方法是把查找区间改成当前数后边。

经改进，代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    long long int a[666666];
    for(int i = 0;i<n;++i) {
        cin>>a[i];
    }
    int m;
    cin>>m;
    sort(a,a+n);
    for(int i = 0;i<n;++i) {
        long long tmp = m-a[i];

        for(int j = i;j<n;++j) {
            if(a[j]==tmp) {
                cout<<a[i]<<" "<<a[j];
                return 0;
            }
        }

    }
    cout<<"No"<<endl;
}