Description 给出一个长度为n的序列a[i]，n+1种硬币，面值分别为1,a[1],a[1]*a[2]，即为a序列的前缀乘积，每种硬币数量无限，要求用最少的硬币凑成s，输出最少硬币数 Input 第一行两个整数n和s表示a序列长度，之后n个整数a[i] (1<=n<=1e5,0<=s<=1e9,2<=a[i]<=1e9) Output 输出所用最少硬币数 Sample Input 3 42 3 2 2 Sample Output 4 Solution 贪心的用面值最大的即可，注意不需要算出所有面值，只要面值超过s的硬币都不要 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111111 int n,a[maxn],s; int main() { while(~scanf("%d%d",&n,&s)) { int pos=0,flag=0; a[0]=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(1ll*a[i]*a[i-1]<=s&&!flag)a[i]*=a[i-1],pos++; else flag=1; } int ans=0; while(s) { ans+=s/a[pos]; s%=a[pos--]; } printf("%d\n",ans); } return 0; }