# C1 - Easy Version
# 题目大意
现在买 n 个东西，每次你可以选择一个非负整数 x，以 3x+1+x×3x−1 的价钱，购买 3x 个物品，请问，如果要使得交易次数最小的话，你要花多少钱？
# 数据范围
- 1≤n≤109
# 题解
显然，按照 n 的三进制来购买物品是能满足交易次数最小的
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| int price[30];
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res = res * a;
a = a * a, b >>= 1;
}
return res;
}
void to_3(int x) {
stack<int> res;
while (x >= 3)
res.push(x % 3), x /= 3;
if (x)
res.push(x);
int ans = 0;
while (res.size()) {
ans += price[res.size() - 1] * res.top();
res.pop();
}
cout << ans << '\n';
}
void solve () {
int x;
cin >> x;
to_3(x);
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
price[0] = 3;
for (int x = 1; x <= 23; x++)
price[x] = qmi(3, x + 1) + x * qmi(3, x - 1);
int _ = 1;
cin >> _;
while(_--)
solve();
return 0;
}
|
# C2 - Hard Version
# 题目大意
在 C1 题的基础上，增加一个正整数 k，题目要求变为，在不超过 k 次交易的情况下，最少花费多少能购买到 n 个物品
# 题解
显然，我们在 C1 里知道了，最少的交易次数是按 n 的三进制来买，所以如果我们的 k 小于三进制下的各位之和，肯定是不能购买的，输出 -1
题目中说了，3x 个物品花费 3x+1+x×3x−1，也就是说，针对 x 的话，单价是 3+3x，随着 x 越大，货物单价也越大
我们不妨从最大的开始往下转移，每往后转移一个单位，会使得交易次数 +2（自身 −1，后者 +3），假设当前的三进制位置是 si
- 如果 si∗2≥ 剩余操作次数，那么全部转移
- 否则只能转移 t=2剩余操作次数 次，也就是说 si 需要 −t，si−1 需要 +2t
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| void solve () {
cin >> x >> k;
vector<int> s;
while (x >= 3) {
int t = x % 3;
s.push_back(t), k -= t, x /= 3;
}
if (x) s.push_back(x), k -= x;
if (k < 0) {
cout << -1 << '\n';
return;
}
for (int i = s.size() - 1; i >= 1; i--) {
if (s[i] * 2 <= k) s[i - 1] += 3 * s[i], k -= s[i] * 2, s[i] = 0;
else {
if (k >= 2) {
int t = k / 2;
s[i] -= t, s[i - 1] += 3 * t;
}
break;
}
}
int ans = 0;
for (int i = 0; i < s.size(); i++) ans += s[i] * price[i];
cout << ans << '\n';
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
price[0] = 3;
for (int x = 1; x <= 23; x++) price[x] = qmi(3, x + 1) + x * qmi(3, x - 1);
int _ = 1; cin >> _;
while(_--) solve();
return 0;
}
|
