2019年4月5日腾讯实习生笔试第1题-凑面值

港控/mmm° 2022-04-24 01:50 182阅读 0赞

/\*  
**题目描述**：  
小Q现在手上有n种不同面值得硬币，每种面值得硬币都有无限多个。  
为了方便购物，小Q希望带尽量多的硬币，并且要能组合出1到m之间（包括1和m）的所有面值

**输入描述:**  
第一行包含两个整数m，n,接下来的n行，每行一个整数  
第i+1行的整数表示第i种硬币的面值。

**输出描述：**  
输出一个整数，表示最少需要携带的硬币数量。如无解，则输出-1

**测试**  
20 4  
1  
2  
5  
10

5  
\*/

//牛客网找的代码，共享出来

//主要思路就是使用一个硬币之前，必须要凑出这个硬币价值 - 1的金钱数目
    #include <iostream>
    #include <climits>
    #include <algorithm>
    #include<vector>
    using namespace std;
    int main() {
    	int m, n;
    	while (cin >> m >> n) {//20 4
    		vector<int> coinbase(n);
    		for (int i = 0; i<n; i++) {
    			cin >> coinbase[i];// 1 2 5 10
    		}
    		if (coinbase[0] != 1) {
    			cout << -1 << endl;
    			continue;
    		}
    		sort(coinbase.begin(), coinbase.end()); //避免输入没有顺序
    			coinbase.push_back(INT_MAX); //防止越界
    			int ptr = 0; //初识硬币指针
    			int count = 0; //计数
    			int now = 0; //当前能凑出来的最大值
    			while (now<m) {
    				int target = m;//期望面值
    				if (coinbase[ptr] - 1 < m)
    					target = coinbase[ptr] - 1;
    				if (now < target) {
    					int gap = target - now;//差距
    					int add = (gap + coinbase[ptr - 1] - 1) / coinbase[ptr - 1];
    					count += add;
    					now += add*coinbase[ptr - 1];
    				}
    				ptr++;
    			}
    		cout << count << endl;
    	}
    }

//还有一种简单的解法也贴出来：  
作者：lyqlola  
来源：CSDN  
原文：[https://blog.csdn.net/lyqlola/article/details/89055772][https_blog.csdn.net_lyqlola_article_details_89055772]

#include <iostream>
    using namespace std;
    int m, n;
    int coin[100];
    
    int main(){
        cin>>m>>n; 
        for(int i=0;i<n;i++) cin>>coin[i];
        sort(coin, coin+n);
        if(coin[0]!=1) return -1;
        int num=0;
        int ans=0;
        int p=0;
        while(num<m){
            while(p+1<n && coin[p+1]<=num+1) p++;
            num+=coin[p];
            ans++;
        }
        cout<<ans<<endl;
        return 0;
    }

[https_blog.csdn.net_lyqlola_article_details_89055772]: https://blog.csdn.net/lyqlola/article/details/89055772