試題 演算法訓練 幸運的店家
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
炫炫開了一家商店，賣的貨只有一個，XXX，XXX賣N元錢，有趣的是，世界上只有面值為3的冪的紙幣，即紙幣只有1元的、3元的、9元的，，，，，有一天，橋神來買XXX，可他沒辦法正好給出N元錢，而炫炫沒法找零，于是他只好用他的錢湊出了一個比N大，并且最小的價值，交給了炫炫，炫炫想知道，他這次最多可以得到多少張紙幣，
輸入格式
一個數，N
輸出格式
一個數，為答案
樣例輸入
4
樣例輸出
2
資料規模和約定
? n<=10^17
思路：
-
答案必不使用1元，可證明：若需要使用若干1元，得到x，滿足x > N，那么去掉1元，得到x1，可能滿足
x1 >= N，當x1 > N，可知x不是最小，當x1 = N，不符合題意， -
3的冪都能由若干3表示，那么要取得最多，就要全部使用3組合(這應該就是貪心的地方)
-
分情況，若N不能被3整除，結果就是
N / 3 + 1，若N能被3整除，則答案是n / 3 + 1(將N的所有3因子除掉后得到n，即n滿足3^k * n = N)如果N能被3整除，那么全用3組合就不符合題意了，而可以用3的某次冪來組合，組合的次數就等于
n / 3 + 1，例：12 = 3 x 4，可以用 3 來組合4，即 3 + 3 , 那么就可以用3 x (3 + 3) = 9 + 9組合 12則最復雜的情況也就是O(\(log_{3}n\))
要點：
- n<=10^17，使用 long long 來讀
代碼：
#include <iostream>
using namespace std;
typedef long long LL;
LL n, res;
int main (){
cin >> n;
if (n % 3) res = (n / 3) + 1;
else {
while (n % 3 == 0) n /= 3;
res = (n / 3) + 1;
}
cout << res << endl;
return 0;
}
吐槽：
這個用搜索的方法幾乎不可能了吧，貪心快但是好難想哇pwp
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/428509.html
標籤：其他
上一篇：演算法基礎知識總結