PAT甲级1048 Find Coins

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]

## 散列解法： ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    { 
        int n,m;
        std::ios::sync_with_stdio(false);
        cin>>n>>m;
        int ha[1005]={ 0};
        for(int i=0;i<n;i++)
        { 
            int temp;cin>>temp;
            ha[temp]++;
        }
        for(int i=1;i<=m/2;i++)
        { 
            if(ha[i]&&ha[m-i])
            { 
                if(i==m-i&&ha[i]<2)continue;
                cout<<i<<" "<<m-i;return 0;
            }
        }
        cout<<"No Solution";
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70_pic_center]

## two pointer解法： ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    { 
        int n,m;
        std::ios::sync_with_stdio(false);
        cin>>n>>m;
        int  temp[n+1];
        for(int i=0;i<n;i++)cin>>temp[i];
        sort(temp,temp+n);
        int i=0,j=n-1;
        while(i<j)
        { 
            if(temp[i]+temp[j]==m)
            { 
                cout<<temp[i]<<" "<<temp[j];return 0;
            }
            else if(temp[i]+temp[j]>m)j--;
            else i++;
        }
        cout<<"No Solution";
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230528/3c3f6896496f446792e6f9fa39646326.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/ecd058bf1fcf4e3da148775b9b719c10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/4c01a3607f9d4383a5e3d5c1786304f8.png