PAT A1048 二分/two points

简单的一道题，想到的有两种方法方法一：二分查找；由于是两个数和，所以我们从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;}