「日常训练」Our Tanya is Crying Out Loud (CFR466D2B)

题意（Codeforces 940B）

对一个数字$x$，你有两个决策：花费$A$减一、或花费$B$除以$k$（但必须可以除尽）。问使之到$1$的最少花费。

分析

贼鸡儿简单，但我花式犯蠢……如果除不尽，那么直接用法一减到可以除得尽的；然后比较法一和法二哪个耗费得少，然后继续如上操作直到$x=1$。典型的贪心算法。
是不是看起来很美？做梦啊！！对于法一，当$x<k$，不能减到除得尽（0）！对于比较耗费，如果$k=1$，只能选择法一，哪怕法二再怎么耗费少都不能啊啊啊啊……
这两个坑踩过去了题目一点难度没有。

源码

#include<bits/stdc++.h>

#define inf 0x3f3f3f3f

#define PB push_back

#define MP make_pair

#define fi first

#define se second

#define lowbit(x) (x&(-x))

#define rep(i, a, b) for(int i = (a); i <= (b); i++)

#define per(i, a, b) for(int i = (a); i >= (b); i--)

#define pr(x) cout << #x << " = " << x << " ";

#define prl(x) cout << #x << " = " << x << endl;

#define ZERO(X) memset((X),0,sizeof(X))

#define ALL(X) X.begin(),X.end()

#define SZ(x) (int)x.size()

using namespace std;

typedef pair<int,int> PI;

typedef pair<pair<int,int>, int> PII;

typedef pair<pair<pair<int,int>, int>, int> PIII;

typedef unsigned long long ull;

typedef long long ll;

typedef long double lb;

#define quickio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

/*      debug("Precalc: %.3f\n", (double)(clock()) / CLOCKS_PER_SEC);

clock_t z = clock();

        solve();

        //debug("Test: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);

*/

template<typename T = int>

inline T read() {

    T val=0, sign=1;

    char ch;

    for (ch=getchar();ch<'0'||ch>'9';ch=getchar())

        if (ch=='-') sign=-1;

    for (;ch>='0'&&ch<='9';ch=getchar())

        val=val*10+ch-'0';

    return sign*val;

}

int main()

{

    ll n,k,A,B;

    cin>>n>>k>>A>>B;

    ll x=n;

    ll ans=0;

    if(k==1)

    {

        ans=A*(x-1); //无能狂怒啊

    }

    else

    {

        while(x!=1)

        {

            if(x%k)

            {

                if(x<k)

                {

                    ans+=(x-1)*A;

                    x=1;

                }

                else

                {

                    ans+=(x%k)*A;

                    x=x-(x%k);

                }

            }

            else

            {

                ans+=min((x/k*(k-1))*A,B);

                x/=k;

            }

            //cout<<x<<endl;

            //assert(x!=0);

        }

    }

    cout<<ans<<endl;

    return 0;

}