PAT A1048 二分/two points-白红宇

PAT A1048 二分/two points

阅读量：5985 次

发布时间：2019-06-20

本文共 1296 字，大约阅读时间需要 4 分钟。

简单的一道题，想到的有两种方法

方法一：二分查找；

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

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        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

第二种方法：two points；

注意的点是避免i=j使得重复加同一个值从而导致错误答案；

#include
    
     #include
     
      #include
      
       #include
       
        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
        
         m){            j--;        }else{            i++;        }    }    if(!flag){        printf("No Solution\n");    }else{        printf("%d %d",coin[i],coin[j]);    }    system("pause");    return 0;}