程序设计与算法（二）算法基础》《第四周二分》和为给定数 4143

今天药忘吃喽~ 2023-08-17 16:23 37阅读 0赞

## 4143:和为给定数 ##

*  [查看][Link 1]
 *  [提交][Link 2]
 *  [统计][Link 3]
 *  [提示][Link 4]
 *  [提问][Link 5]

总时间限制:

1000ms

内存限制:

65536kB

描述

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

输入

共三行：  
第一行是整数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

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    int a[100006];
    int output[100006];
    /*
    方法1： 二分查找
    */
    bool func(int a[],int sum,int size, int output[])
    {
        int m,i;
        int left, right, mid;
    
        for (i = 0; i < size - 2; i++)
        {
            m = sum - a[i];
            left = i + 1;
            right = size - 1;
            while (left <= right)
            {
                mid = left + (right - left) / 2;
                if (a[mid] == m)
                {
                    output[0] = a[i];
                    output[1] = m;
                    return true;
                }
                else if (a[mid] > m)
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
    
            }
        }
        /*
        倒数2个数不用二分查找了，直接加一下就好了，节省计算量
        */
        if ((a[size - 2] + a[size - 1]) == sum)
        {
            output[0] = a[size - 2];
            output[1] = a[size - 1];
            return true;
        }
    
        return false;
    
    }
    /*
    查找的时候，设置两个变量 i 和 j，i 初值是0，j 初值是 n-1，
    看 a[i]+a[j]，如果大于 m，就让 j 减1，如果小于 m，就让 i 加1，
    直至 a[i]+a[j]=m
    */
    bool func2(int a[], int sum, int size, int output[])
    {
        int i=0, j=size-1;
        while (i < j)
        {
            if ((a[i] + a[j]) == sum)
            {
                output[0] = a[i];
                output[1] = a[j];
                return true;
    
            }
            else if ((a[i] + a[j]) > sum)
            {
                j--;
            }
            else
            {
                i++;
            }
        }
        return false;
    }
    
    int main()
    {
        int size, sum;
        cin >> size;
        for (int i = 0; i < size; i++)
        {
            cin >> a[i];
        }
        cin >> sum;
    
        sort(a, a + size ); //将输入数据从小到大排序
    
        //bool res = func(a, sum, size, output);
        bool res = func2(a, sum, size, output);
        if (res == true)
            cout << output[0] << " "<<output[1] << endl;
        else
            cout << "No";
        return 0;
    }

转载于:https://www.cnblogs.com/focus-z/p/11518915.html

[Link 1]: http://bailian.openjudge.cn/practice/4143/
[Link 2]: http://bailian.openjudge.cn/practice/4143/submit/
[Link 3]: http://bailian.openjudge.cn/practice/4143/statistics/
[Link 4]: http://bailian.openjudge.cn/practice/hint/4143/
[Link 5]: http://bailian.openjudge.cn/practice/clarify/4143/