找硬币

哈希

发布日期: 2021-10-14

文章字数: 592

阅读次数:

找硬币

伊娃喜欢从整个宇宙中收集硬币。

有一天，她去了一家宇宙购物中心购物，结账时可以使用各种硬币付款。

但是，有一个特殊的付款要求：每张帐单，她只能使用恰好两个硬币来准确的支付消费金额。

给定她拥有的所有硬币的面额，请你帮她确定对于给定的金额，她是否可以找到两个硬币来支付。

输入格式

第一行包含两个整数 N 和 M，分别表示硬币数量以及需要支付的金额。

第二行包含 N 个整数，表示每个硬币的面额。

输出格式

输出一行，包含两个整数 V1,V2，表示所选的两个硬币的面额，使得 V1≤V2 并且 V1+V2=M。

如果答案不唯一，则输出 V1最小的解。

如果无解，则输出 No Solution。

数据范围

1≤N≤105,
1≤M≤1000

输入样例1：

8 15
1 2 8 7 2 4 11 15

输出样例1：

4 11

输入样例2：

7 14
1 8 7 2 4 11 15

输出样例2：

No Solution

题外话

因为，本想着要一直坚持每日更新dp的题目的，但是一是因为dp的题目难度不小，二是还有很多其他值得记录的题目，所以，dp就随缘更新吧，但是每日刷题是必须的，等下次找到很妙，或者是有共性的dp问题，我再打卡吧。

本题还是比较水的一道题目，其实有点像leetcode的第一题，两数之和的题目。但是leetcode的那一题给的数据范围比较宽泛，本题是105，所以时间复杂度为2的算法就过不了。

好吧，这时候hash表就要派上用场了。

我们可以将值作为key存入hash表，然后value就是他的下标。我们可以进行依次遍历，然后用hash的find函数，找到hash表中是否有与他进行配对的值。若有直接返回下标。若没有，就直接cout No Solution .

贴个代码：

#include 

using namespace std ;

const int N = 100010 ; 

unordered_map ha ; 

int a[N] ; 
int main()
{
    int n , target ; 
    cin >> n >> target ; 
    
    for(int i = 1 ; i <= n ; ++ i)
    {
        cin >> a[i] ; 
    }
    
    sort(a , a+n+1) ; 
    
    for(int i = 1 ; i <= n ; ++ i)
    {
        ha[a[i]] = i  ; 
    } 
    
    int id1  , id2 ; 
    
    for(int i = 1 ; i <= n ; ++ i)
    {
        auto pos = ha.find(target-a[i]) ;
        
        if(pos != ha.end() && pos->second != i)
        {
            id1 = i ; 
            id2 = pos->second ; 
            cout << a[id1] << " " << a[id2]  ; 
            return 0 ;
        }
    }
    
    cout << "No Solution" << endl ; 
    return  0 ; 
}