题目传送门

思路

题目大意

你需要买

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：

CPP

#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;
}

CF2132C1 The Cunning Seller (easy version)

文章操作

题目传送门

思路

题目大意

做法

AC Code：

相关推荐

评论

CF2132C1 The Cunning Seller (easy version)