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

欢迎查看原题

1.简单题目叙述

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

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

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

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

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

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

样例输入

样例输出

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 \times 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;

}

巴特西

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

1.简单题目叙述

初步思路：

最新文章

热门文章