PAT A1048 二分/two points

小灰灰 2021-09-18 12:16 167阅读 0赞

![clipboard.png][]  
简单的一道题，想到的有两种方法

方法一：二分查找；  
由于是两个数和，所以我们从i=1开始枚举，在剩下的i+1~n序列中找到m-a\[i\]的数，是一个递增不重复序列的查找问题，之前二分法总结过，所以不再赘述；  
代码如下：

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    const int maxn=100010;
    int coin[maxn];
    int n,m;
    
    int binarySearch(int l,int r,int x){
        while(l<=r){
            int mid=(l+r)/2;
            if(coin[mid]==x)
                return mid;
            else if(coin[mid]>x){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return -1;
    }
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&coin[i]);
        }
        int a,b;
        int r=-1;
        sort(coin+1,coin+n+1);
        for(int i=1;i<n;i++){
            a=coin[i];
            b=m-coin[i];
            r=binarySearch(i+1,n+1,b);
            if(r!=-1){
                break;
            }
        }
        if(r==-1){
            printf("No Solution\n");
        }else{
            printf("%d %d",a,b);
        }
        system("pause");
        return 0;
    }

第二种方法：two points；  
注意的点是避免i=j使得重复加同一个值从而导致错误答案；

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    const int maxn=100010;
    int coin[maxn];
    int n,m;
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&coin[i]);
        }
        int a,b;
        int r=-1;
        sort(coin+1,coin+n+1);
        int i=1,j=n;
        int sum;
        bool flag=false;
        while(i<j){
            sum=coin[i]+coin[j];
            if(sum==m){
                flag=true;
                break;
            }
            else if(sum>m){
                j--;
            }else{
                i++;
            }
        }
        if(!flag){
            printf("No Solution\n");
        }else{
            printf("%d %d",coin[i],coin[j]);
        }
        system("pause");
        return 0;
    }

[clipboard.png]: /images/20210726/6e67560e4e604c438fec1fde7274f421.png