非 暴 力 不 A C
题目链接
https://codeforces.com/contest/1311/problem/D
题意
输入三个整数\(1\le a\le b\le c\le10^4\)，每次操作可任意选定其中一个整数，作\(+1/ -1\)的操作，只要操作不产生一个非正数，那么就是合法的。问最少经过多少次合法的操作，产生出的新的\(A\le B\le C\)，且\(B\)是\(A\)的倍数，\(C\)是\(B\)的倍数。输出次数与相应的\(A、B、C\).
我的解题脑回路
第一反应是，最少的次数，是不是BFS啊？后仔细一想，不对，要是以ABC为状态进行BFS，复杂度怕是得爆炸。于是开始找规律，是不是先调整a呢，还是先调整c呢，或者先调整b呢？然后脑补出一系列的规律，但是都被自己叉掉了。终于，我，停止了思考。 （卡兹sama觉得很赞）
真正的题解
··遂答应blb带他上分，换来了解题思路··
数据范围！数据范围！数据范围！
\(10^4\)的范围，只要低于\(O(n^2)\)就基本可以。所以从1~10000直接暴力枚举A；再对于每个A，继续枚举B（这里只需枚举所有的A的倍数即可）；接着，对于每组A，B，枚举C的操作是\(O(1)\)的：因为C只需是离c最近的B的倍数即可，可用min(c%B, B - c%B)表示。
有n个A要枚举，对于每个A，需要枚举B的数量是n/A，而枚举C为\(O(1)\)，这样枚举的复杂度是：
\[
\sum^n_{A=1}{\frac nA\cdot O(1)}=n\cdot \sum^n_{i=1}{\frac 1i}=O(n\cdot log\ n)
\]
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
const int MAX = 10000;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int a, b, c;
int res_a, res_b, res_c;
scanf("%d %d %d", &a, &b, &c);
int mmin = 40000;
for (int i = 1; i <= MAX; i++) {
int cnt_a = abs(a - i);
for (int j = i; j <= 2 * MAX; j += i) {
int cnt_b = abs(j - b);
int cnt_c;
int k;
if (c <= j) {
cnt_c = j - c;
k = j;
}
else {
cnt_c = min(c % j, j - c % j);
k = c % j < j - c % j ? c / j * j : (c / j + 1) * j;
}
int cnt = cnt_a + cnt_b + cnt_c;
if (cnt < mmin) {
mmin = cnt;
res_a = i;
res_b = j;
res_c = k;
}
}
}
printf("%d\n", mmin);
printf("%d %d %d\n", res_a, res_b, res_c);
}
return 0;
}
|