蓝桥杯练习系统（算法训练）ALGO-985 幸运的店家

本文主要是介绍蓝桥杯练习系统（算法训练）ALGO-985 幸运的店家，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　炫炫开了一家商店，卖的货只有一个，XXX，XXX卖N元钱。有趣的是，世界上只有面值为3的幂的纸币，即纸币只有1元的、3元的、9元的。。。。，有一天，桥神来买XXX，可他没办法正好给出N元钱，而炫炫没法找零，于是他只好用他的钱凑出了一个比N大，并且最小的价值，交给了炫炫。炫炫想知道，他这次最多可以得到多少张纸币。

输入格式

　　一个数，N

输出格式

　　一个数，为答案

样例输入

4

样例输出

2

数据规模和约定

　　n<=10^17

#include<iostream>
using namespace std;int main(){long long int n;scanf("%lld",&n);if(n%3){printf("%lld\n",n/3+1);}else{while(n%3==0){n/=3;}printf("%lld\n",n/3+1);}
}

 思路：

1、不可能有1元面值的；

2、对于N=3n+1，3n+2（不是3的倍数），尽可能多得用3元面值，因此付3n+3元，即n+1张；

3、对于N=3n（是3的倍数），此时不能全用3元面值了，得用3的幂面值的（比如9,27,……）。举个例子：12=3×4+0，就不能用4张3元面值，我们可以把4扩大成3+3（按照2中N不是3的倍数进行），因此付3×（3+3）=9+9，即2张。所以，这里不能被3整除的4决定最终答案。

这篇关于蓝桥杯练习系统（算法训练）ALGO-985 幸运的店家的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---