陌生银行(ATCODER初学者竞赛099)

为增加取款难度,某银行在一次操作中只允许客户取款下列金额之一:

1日元(日本货币)

6日元,6日元 ^ 2(=36)日元,6 ^ 3(=216)日元,…

9日元,9日元 ^ 2(=81)日元,9 ^ 3(=729)日元,…

总共需要多少次操作才能提取N日元?

取款的钱不准再存。

约束条件 1≤N≤100000 n是一个整数。

标准输入的输入格式如下:

n 产量 如果至少需要X个操作才能总共提取N日元,请打印X。

样本输入1 一百二十七 样本输出1 四 取1日元,9日元,36(=6 ^ 2)日元和81(=9 ^ 2)日元,我们可以在四次操作中撤回127日元。

对我来说,这似乎是一个简单的贪心问题,这就是我使用的方法,但我发现我为一个样本得到了不同的结果,并得出结论。 它不会总是贪婪的。

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std;


int intlog(int base, long int x) {
return (int)(log(x) / log(base));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

long int n;cin>>n;

int result=0;
while(n>0)
{
int base_9=intlog(9,n);int base_6=intlog(6,n);
int val;
val=max(pow(9,base_9),pow(6,base_6));
//cout<<pow(9,base_9)<<" "<<pow(6,base_6)<<"\n";
val=max(val,1);
if(n<=14 && n>=12)
    val=6;
n-=val;
//cout<<n<<"\n";
result++;
}
cout<<result;
return 0;
}

在n 14和大于12时,我们必须选择6而不是9,因为要达到零,它将采取较少的步骤。

只有18/22个TCS有交流电,请帮助我理解我的错误。