题意
给出你一个数，问你这个数最少能用多少个数（可以重复）的阶乘表示出来。
思路
使用一种简单的贪心策略：
从一个刚好比给出的数小的阶乘开始，不断尝试减掉较大的阶乘，直到将给出的数减为0 。
这个贪心策略是合理的，因为如果我们当前可以减掉n!，我们减掉(n-1)!一定不如减掉n!优，因为n!=n*(n-1)!，相当于我们多减了n次，所以我们要减掉n!才能保证最优。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include<iostream> using namespace std; const int mxa = 10; int sum[mxa]; void Premake(){ sum[1] = 1; for(int i=2;i<mxa;i++) sum[i] = sum[i-1]*i; } int main(){ Premake(); int input; while(cin >> input){ int ans = 0; int last = 8; while(input && last){ if(input < sum[last]){ last -= 1; continue; } input -= sum[last]; ans ++; } cout << ans << endl; } return 0; } |
