CF2132C1 The Cunning Seller (easy version)

Andy1101 · 2025-08-23 19:31:44 · 题解

题目传送门

思路

题目大意

你需要买 n 个西瓜，每次可以买 3^x 个西瓜（1 \le 3^x \le n），需要花费 3^{x+1} + x \times 3^{x-1} 个硬币，问在交易次数最少的前提下的最少花费是多少。

做法

由于是在交易次数最少的前提下，所以购买的方式也是唯一的。于是我们可以将 n 转化成三进制数，对于第 i 位的数字 j，需要 j \times (3^{x+1} + x \times 3^{x-1}) 的花费。

tips：可以预处理 3 的幂。

AC Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30+5;
ll t[N]; //t[i]表示3的i次方 
void solve()
{
    int n;
    cin >>n;
    ll ans=0;
    for(int i=18;i>=0;i--)
    {
        if(n>=t[i])
        {
            ll tmp=n/t[i]; 
            n-=(tmp*t[i]);
            ans=ans+(t[i+1] + i*t[i-1])*tmp; //*tmp 表示需要重复多少次这样的交易 
        }
    }
    cout <<ans<<'\n';
}
int main()
{
    t[0]=1;
    for(int i=1;i<=20;i++) t[i]=t[i-1]*3; //预处理3的i次方 
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}