AcWing每日一题--找硬币

https://www.acwing.com/problem/content/1534/

算法一：hashmap

对于每一个数a，看m-a是否出现过。取其中的a最小的值。

 1 #include<iostream>
 2 #include<unordered_set>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=1e5+10,INF=1010;
 6 int main(void){
 7     int n,m;
 8     cin>>n>>m;
 9     int v1=INF,v2;
10     unordered_set<int> hash;
11     for(int i=0;i<n;i++){
12         int a,b;
13         cin>>a;
14         b=m-a;
15         if(hash.count(b)){
16             int c=min(a,b),d=max(a,b);
17             if(v1>c){
18                 v1=c,v2=d;
19             }
20         }
21         hash.insert(a);
22     }
23     if(v1!=INF){
24         cout<<v1<<" "<<v2;
25     }else{
26         cout<<"No Solution";
27     }
28     return 0;
29 }

2、双指针算法

发现性质，排序之后，l指针后移，r指针必定前移，故可用双指针算法将时间复杂度控制在O(n)内。

 1 #include<algorithm>
 2 #include<iostream>
 3 using namespace std;
 4 const int N=1e5+10;
 5 int a[N];
 6 int main(void){
 7     int n,m;
 8     cin>>n>>m;
 9     for(int i=0;i<n;i++){
10         cin>>a[i];
11     }
12     sort(a,a+n);
13     int l=0,r=n-1;
14     while(l<r){
15         while(l<r&&a[l]+a[r]>m)
16             r--;
17         if(l<r&&a[l]+a[r]==m){
18             cout<<a[l]<<" "<<a[r];
19             return 0;
20         }
21         l++;
22     }
23     cout<<"No Solution";
24     return 0;
25 }

3、二分

排序之后，对于每一个数找在其之后的数，判断是否合法。

 1 #include<algorithm>
 2 #include<iostream>
 3 using namespace std;
 4 const int N=1e5+10;
 5 int a[N];
 6 int main(void){
 7     int n,m;
 8     cin>>n>>m;
 9     for(int i=0;i<n;i++){
10         cin>>a[i];
11     }
12     sort(a,a+n);
13     for(int i=0;i<n;i++){
14         int b=m-a[i];
15         int pos=lower_bound(a+i+1,a+n,b)-a;
16         if(a[i]+a[pos]==m){
17             cout<<a[i]<<" "<<a[pos];
18             return 0;
19         }
20     }
21     cout<<"No Solution";
22     return 0;
23 }

或者手写

 1 #include<algorithm>
 2 #include<iostream>
 3 using namespace std;
 4 const int N=1e5+10;
 5 int a[N];
 6 int binary_search(int l,int r,int tar){
 7     while(l<r){
 8         int mid=l+r+1>>1;
 9         if(a[mid]>tar){
10             r=mid-1;
11         }else{
12             l=mid;
13         }
14     }
15     return l;
16 }
17 int main(void){
18     int n,m;
19     cin>>n>>m;
20     for(int i=0;i<n;i++){
21         cin>>a[i];
22     }
23     sort(a,a+n);
24     for(int i=0;i<n;i++){
25         int b=m-a[i];
26         int pos=binary_search(i+1,n-1,b);
27         if(a[i]+a[pos]==m){
28             cout<<a[i]<<" "<<a[pos];
29             return 0;
30         }
31     }
32     cout<<"No Solution";
33     return 0;
34 }