蓝桥杯 ALGO-985 幸运的店家(贪心)

试题 算法训练 幸运的店家

资源限制

时间限制:1.0s 内存限制:256.0MB

问题描述

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

输入格式

  一个数,N

输出格式

  一个数,为答案

样例输入

4

样例输出

2

数据规模和约定

​ n<=10^17


思路:

  1. 答案必不使用1元,可证明:若需要使用若干1元,得到x,满足x > N。那么去掉1元,得到x1,可能满足x1 >= N,当x1 > N,可知x不是最小,当x1 = N,不符合题意。

  2. 3的幂都能由若干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\))


要点:

  1. 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;
}


蓝桥杯 ALGO-985 幸运的店家(贪心)


吐槽:

这个用搜索的方法几乎不可能了吧,贪心快但是好难想哇pwp

上一篇:(转)列举ASP.NET 页面之间传递值的几种方式


下一篇:IIS HTTP Error 500.24