Description 梦幻王国钱币面值有五种1、7、49、343、2401（即：7^0、7^1、7^2、7^3、7^4）。某人买东西要用现金支付n元，买卖双方可以相互找钱（假设双方各种钱币数量都足够多）。 问：买卖双方最少总共需用多少张钱币？ Input n(n<=3000) Output 最少钱币数 Sample Input 12 Sample Output 4 HINT [样例解释] 买方用2张7元；卖方找2张1元，共4张钱币 [数据范围] 对于50%的数据，n,m<=1500 对于100%的数据，n,m<=3000

The Solution

这道题的思想很显然。

首先，你先把钱数转化为7进制。如（672）10=（1650）7

然后先求单方面给，就是纯加法的运算，这很简单，只需要将7进制下的数字和求出来即可。1+6+5=12。

下一步，就要用到找钱了。思想核心就在这里。怎么找钱呢？

我们先看看如果单看七进制一位上的数字。可以得到4是中间数，这个数无论是纯加法还是找钱所需张数都一样。

即我可以给4张，也可以给你一张比当前大一个面值的，再由你找3张。 便于理解，我举例：钱数是11，7进制是14。不看要给的7块，单从剩余4块分析，我可以给4张1块，也可以给1张7块，你找3张一快，钱的张数都是4。

综上，我们推知，当单个位上的数字≤4的时候，我们可利用纯加法（既然都一样用简单的），当数字＞4的时候，我们就用找钱。

继续开头的例子。(1650)7，6>4，5>4，所以应该找钱。怎么找呢？6进一位，所以要给一张7^3也就是343元的代替了6张49元，5进一位，所以也要给一张49元的代替5张7元。

看下面的表格

number7^4=24017^3=3437^2= 497^1= 77^0= 1给钱21找钱12

我们发现，给一张49又找一张49，抵消了；给一张7找2张7，抵消了一张。 因此，我们可以把各个位上给钱和找钱的差的绝对值加起来，2+2=3张。 我们来验证一下。672=343*2-7*2。没错。

不懂看标，嘿嘿嘿嘿

Code

c++

#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #define fo(i,a,b) for (int i=a;i<=b;i++) #define fd(i,a,b) for (int i=a;i>=b;i--) #define N 30005 using namespace std; int a[N]; int main() { int n,k=0,ans=0; scanf("%d",&n); for (;n;n/=7) a[++k]=n%7; fo(i,1,k) { if (a[i]>=4) a[i]=7-a[i],a[i+1]++; ans+=a[i]; } printf("%d",ans); }

Pascal

var n,i,j,k,ans:longint; a:array[0..30000] of longint; begin readln(n); for i:=1 to n do begin k:=k+1; a[k]:=n mod 7; n:=n div 7; end; for i:=1 to k do begin if a[i]>=4 then begin a[i]:=trunc(7)-a[i]; a[i+1]:=a[i+1]+1; end else; ans:=ans+a[i]; end; ans:=ans+a[k]; writeln(ans); end.