PAT甲级1048 Find Coins

朱雀 2023-07-24 14:33 189阅读 0赞

在这里插入图片描述

散列解法：

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int main()
  5. { 
  6.     int n,m;
  7.     std::ios::sync_with_stdio(false);
  8.     cin>>n>>m;
  9.     int ha[1005]={ 0};
  10.     for(int i=0;i<n;i++)
  11.     { 
  12.         int temp;cin>>temp;
  13.         ha[temp]++;
  14.     }
  15.     for(int i=1;i<=m/2;i++)
  16.     { 
  17.         if(ha[i]&&ha[m-i])
  18.         { 
  19.             if(i==m-i&&ha[i]<2)continue;
  20.             cout<<i<<" "<<m-i;return 0;
  21.         }
  22.     }
  23.     cout<<"No Solution";
  24.     return 0;
  25. }

在这里插入图片描述

two pointer解法：

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int main()
  5. { 
  6.     int n,m;
  7.     std::ios::sync_with_stdio(false);
  8.     cin>>n>>m;
  9.     int  temp[n+1];
  10.     for(int i=0;i<n;i++)cin>>temp[i];
  11.     sort(temp,temp+n);
  12.     int i=0,j=n-1;
  13.     while(i<j)
  14.     { 
  15.         if(temp[i]+temp[j]==m)
  16.         { 
  17.             cout<<temp[i]<<" "<<temp[j];return 0;
  18.         }
  19.         else if(temp[i]+temp[j]>m)j--;
  20.         else i++;
  21.     }
  22.     cout<<"No Solution";
  23.     return 0;
  24. }

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读