目录
引言：
ACM临近了，那么C语言的部分就暂时先不更新了，我们来通过一个月的训练，争取拿一个ACM的省铜，那么，之后这一个月的时间里，我所发的博客的题目来源于codeforces（即cf）中，难度区间呢，在1300-1500之间，将这个难度区间的题基本能打出来，那么省铜一般也是稳了，那么，怎么筛选难度呢，在这里，在俩个框框中输入难度区间即可，如图
那么，我们选完填完1300-1500后，即可开始刷题
今日，我们要讲的是难度评定在1400的一道题The Cunning Seller (hard version)
这道题真的挺折磨我的，思路其实是好想的，但是细节方面还是比较多的，也可能是我太菜了，给你们看看我连wa9次的超神战绩
接下来，我们就来讲一讲这个题，顺便讲讲我踩的种种坑————>
注：解题用的Ｃ＋＋
正文：
那么，我们正式开始讲解这道题，我们先来分析一下题目
题意分析
这是题目链接Problem - 2132C2 - Codeforces
不想跳转可看下图
那么，我们可以先结合题目与样例的解说可以得到，题目中的 n 表示需要买的西瓜，k 表示可以分多少批来购买西瓜，然后每次买西瓜的数量一定要是３的指数次幂，即３的ｘ次。然后题目问我们最终是否可以在指定的批次内买到指定的西瓜数量，并且要使花的钱最少，那么，这就是这个题目的主要要求
接下来，我们对该要求的实现进行逻辑推理，然后再将推理出的逻辑用代码表示出来即可
逻辑梳理
首先，我们来看一下买不同指数幂的西瓜跟价钱的关系，如图
通过上述的推算，我们可以知道，在同样的西瓜的数量下，若指数幂为ｘ＋１级，则需要３个指数幂为ｘ级来等价，通过运算可知，ｘ＋１的指数幂所花的钱比ｘ指数幂所花的钱多３的ｘ指数幂，且西瓜数量是一样的，所以指数次数越低，所花的钱就越少。
那么，接下来，我们来想次数的关系，我们可以通过将ｎ转为三进制，这样，就可以得出若要购买ｎ西瓜所需要的最小交易次数，即各个位上的数相加（原因也在上述推算中得出，三个低指数幂西瓜量等于一个高指数幂西瓜量），然后通过最小交易次数的比较，来判断是否可以达成交易，
若能达成，就对三进制进行压缩，即把一个高位，拆成对应的３个低位（即多俩次交易次数），然后减去便宜了多少钱，一直压缩至次数压缩完或已经压缩到最小
若不能达成，只需要输出＂－１＂即可
那么逻辑已经整理完了，我们来讲一讲代码的实现
代码实现
我们通过逻辑梳理，可以总结出，其实要实现这个代码需要注意的只有俩个部分，一个便是将ｎ变为三进制并存起来，还有一个便是对三进制的ｎ进行操作，那么我们开始教学
首先我们在全局变量处写上ｔ，ｎ，ｋ，以及数组 san[100]
ｔ，ｎ，ｋ 顾名思义，就是样例个数，要买的西瓜数和可交易次数
san[100] 即将n转换为三进制后存放的位置，为什么设为100，因为n的数据范围到1e9，但2的31次就跟1e9差不多了，那么3的指数幂肯定比2更快到1e9，但为了美观，所以我写了100
转三进制与交易次数和钱的预处理
接下来就是将n转变为三进制后存入数组即可，这部分代码如下，那我们来解释一下这个代码
memset(san, 0, sizeof(san));
int wei = 0;
cin >> n >> k;
for (wei = 0; pow(3, wei) <= n; wei++);
wei--;
int tou = wei;
long long ci = 0;
long long ans = 0;
while (n)
{
int i = 0;
for (i = 0; i <= 3; i++)
{
if (i * pow(3, wei) > n)
break;
}
i--;
ci += i;
ans += i * (pow(3, wei + 1) + wei * pow(3, wei - 1));
san[wei] = i;
n -= i * pow(3, wei);
wei--;
}首先对san数组进行预处理（必须进行预处理，因为不预处理会出事，具体我会在我的错误分析中讲解）
然后wei代表的是n转变成三进制后的最高位，随后输入n和k，通过循环先找到最高位用wei表示
然后用tou给wei赋值，用于之后的对进制压缩操作，为什么还要再赋一个值，因为wei在之后要进行操作， 会导致使用出现问题，所以用tou给wei赋值
随后俩个变量
ci 表示交易的次数
ans 表示需要花费的钱
随后用一个while循环，将n转换为三进制，并算出最少交易次数ci以及在最少交易次数时所花的钱ans
在三进制存完以及各类变量与处理完后，就可以进行核心代码（即进制退位）的编写了
进制退位（核心）
接下来就是最核心的进制退位过程了，因为我们已经得出一个高指数幂的数量相当于3个低指数幂的和，但金钱相差是3的低指数幂次，所以可以进行退位，以一换三，买的数量不变，但花的钱变少，唯一的条件知识可交换次数需要大于2（取消高指数幂的1次购买，换3次低指数幂的购买，净差2次交易次数），那么，代码如下，我们对着代码来进行分析
ci = k - ci;
if (ci < 0)
cout << "-1" << endl;
else
{
while (ci >= 2 && tou > 0)
{
if (ci - san[tou] * 2 >= 0)
{
ci -= san[tou] * 2;
san[tou - 1] += 3 * san[tou];
ans -= san[tou] * pow(3, tou - 1);
}
else
{
ci = ci / 2;
ans -= ci * pow(3, tou - 1);
ci = 0;
}
tou--;
}
cout << ans << endl;
}首先，将ci赋值为ｋ－ｃｉ。算出剩余的可交易次数
若交易次数比0 小，则输出-1即可，因为连最低交易次数都无法达到
若交易次数非0，就进行操作
经过我上面的讲述，需要将交易剩余次数要确保在2次以上，并且进制所在位不能在0位上（因为0位上的无法再进行退位，已经退到了末路），然后用一个循环，讲这俩个条件包括起来后，在循环内部再进行操作即可
因为退一次位，需要2次交易次数，且，前一位的san会多3，所以我们可以用分支语句来进行操作，若剩余次数可以将当前位的全部退位，就进行正常操作，若不能全部退位，就只进行部分操作后结束即可，这就是上方代码中的分支语句作用。
那么到这里，该题的核心就全部讲完了，接下来就是源码环节
源代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
int t, n, k;
long long san[100];
int main()
{
cin >> t;
while (t--)
{
memset(san, 0, sizeof(san));
int wei = 0;
cin >> n >> k;
for (wei = 0; pow(3, wei) <= n; wei++);
wei--;
int tou = wei;
long long ci = 0;
long long ans = 0;
while (n)
{
int i = 0;
for (i = 0; i <= 3; i++)
{
if (i * pow(3, wei) > n)
break;
}
i--;
ci += i;
ans += i * (pow(3, wei + 1) + wei * pow(3, wei - 1));
san[wei] = i;
n -= i * pow(3, wei);
wei--;
}
ci = k - ci;
if (ci < 0)
cout << "-1" << endl;
else
{
while (ci >= 2 && tou > 0)
{
if (ci - san[tou] * 2 >= 0)
{
ci -= san[tou] * 2;
san[tou - 1] += 3 * san[tou];
ans -= san[tou] * pow(3, tou - 1);
}
else
{
ci = ci / 2;
ans -= ci * pow(3, tou - 1);
ci = 0;
}
tou--;
}
cout << ans << endl;
}
}
return 0;
}
那么源码讲完了，看着挺简单的，为什么我能WA这么多次呢，那么就进入错误分析环节，一开始我找自己错误时候是真的艰巨，后面的问题，倒是容易解决
错误分析
san数组重置的重要性
我在一开始的时候，思路便以明确，但在代码执行的过程中，却出了点意外，这个意外是真的难找，那么，就让我们看看第一次我提交时的源码以及错误样例
源代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
int t, n, k;
long long san[100];
int main()
{
cin >> t;
while (t--)
{
int wei = 0;
cin >> n >> k;
for (wei = 0; pow(3, wei) <= n; wei++);
wei--;
int tou = wei;
long long ci = 0;
long long ans = 0;
while (n)
{
int i = 0;
for (i = 0; i <= 3; i++)
{
if (i * pow(3, wei) > n)
break;
}
i--;
ci += i;
ans += i * (pow(3, wei + 1) + wei * pow(3, wei - 1));
san[wei] = i;
n -= i * pow(3, wei);
wei--;
}
ci = k - ci;
if (ci < 0)
cout << "-1" << endl;
else
{
while (ci >= 2 && tou > 0)
{
while (san[tou] && ci >= 2)
{
ci -= 2;
san[tou]--;
san[tou - 1] += 3;
ans -= pow(3, tou - 1);
}
tou--;
}
cout << ans << endl;
}
}
return 0;
}错误样例
因为错误在第二个样例中的第388个数据，所以想找也找不到，没招，我就开始研究
思来想去，就只有pow会吞精度的可能导致判断出问题，于是我后面又进行了将pow强转long long，或者不用pow，使用循环达到pow的效果，但最终依旧WA在了这个地方，后面因为一直找不出问题，这题也停滞了一段时间
为何这题数组重制很重要
随后，我在今天看到时候，突然发现了在转三进制部分的while循环的代码的漏洞，若不对san数组进行重置，就会导致上一个的san数组中的数据是被保留下来的，但因while的判断条件是n，就导致若n为0后，循环就结束了，但若是n在不是最低位才为0，而是在前面就为0了，就会导致提前退出循环，没有将后面低位的数组中的数值清0，最终会导致计算初ans值的时候以及后续对位进行退位操作时数据变化的影响
所以san数组重置是非常必要的
注：但也不是一定要重置，也可以将while循环的判断条件改为wei>=0,这样就可以使数组全部初始化，只是这样内部的代码就也需要更改一下了
超时问题
在解决上面的重置问题后，我又交了一发，结果超时了，但这个问题就很简单了，就只需要对循环嵌套深的，且可以优化的部分进行优化即可，那么我们看下面源码进行分析
源代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
int t, n, k;
long long san[1000];
int main()
{
cin >> t;
while (t--)
{
memset(san, 0, sizeof(san));
int wei = 0;
cin >> n >> k;
for (wei = 0; pow(3, wei) <= n; wei++);
wei--;
int tou = wei;
long long ci = 0;
long long ans = 0;
while (n)
{
int i = 0;
for (i = 0; i <= 3; i++)
{
if (i * pow(3, wei) > n)
break;
}
i--;
ci += i;
ans += i * (pow(3, wei + 1) + wei * pow(3, wei - 1));
san[wei] = i;
n -= i * pow(3, wei);
wei--;
}
ci = k - ci;
if (ci < 0)
cout << "-1" << endl;
else
{
while (ci >= 2 && tou > 0)
{
while (san[tou] && ci >= 2)
{
ci -= 2;
san[tou]--;
san[tou - 1] += 3;
ans -= pow(3, tou - 1);
}
tou--;
}
cout << ans << endl;
}
}
return 0;
}分析
通过上面的代码与AC代码的比对，我们会发现，其实没什么区别，主要区别便是在这个俩层循环的优化，如图，这部分的优化就很容易懂了，在代码实现里也讲过了，就不过多叙述了
结语：
那么，今日算法题的讲解就结束了，希望对你们有所帮助，谢谢观看，感觉不错可以分享给朋友一起看哟
