【PAT甲级】1048 Find Coins (25 分)(二分)

题意:

输入两个正整数N和M(N<=10000,M<=1000),然后输入N个正整数(<=500),输出两个数字和恰好等于M的两个数(小的数字尽可能小且输出在前),如果没有输出"No Solution"。

AAAAAccepted code:

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int a[100007];
 5 int main(){
 6     ios::sync_with_stdio(false);
 7     cin.tie(NULL);
 8     cout.tie(NULL);
 9     int n,k;
10     cin>>n>>k;
11     for(int i=1;i<=n;++i)
12         cin>>a[i];
13     sort(a+1,a+1+n);
14     int ans=0;
15     for(int i=1;i<=n;++i){
16         int l=1,r=n;
17         while(l<=r){
18             int mid=(l+r)>>1;
19             if(mid!=i){
20                 if(a[i]+a[mid]<k)
21                     l=mid+1;
22                 if(a[i]+a[mid]>k)
23                     r=mid-1;
24                 if(a[i]+a[mid]==k){
25                     ans=a[mid];
26                     break;
27                 }
28             }
29             if(mid==i){
30                 if(a[i]+a[mid-1]<k)
31                     l=mid+1;
32                 if(a[i]+a[mid-1]>k)
33                     r=mid-1;
34                 if(a[i]+a[mid-1]==k){
35                     ans=a[mid-1];
36                     break;
37                 }
38             }
39         }
40         if(ans){
41             cout<<a[i]<<" "<<ans;
42             return 0;
43         }
44     }
45     cout<<"No Solution";
46     return 0;
47 }
保持热爱 不懈努力 不试试看怎么知道会失败呢(划掉) 世上无难事 只要肯放弃(划掉)
原文地址:https://www.cnblogs.com/ldudxy/p/11616715.html