-
Notifications
You must be signed in to change notification settings - Fork 1
/
q1.cpp
95 lines (84 loc) · 2.16 KB
/
q1.cpp
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <string>
using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::string;
// 1:Shredding Company
// 将一串数字分割,使得分割后的数字和最接近 target(不大于)
// 1. 如果数字正好等于target,则不会剪切
// 2. 如果多种最接近target的方案,则输出 rejected
// 3. 如果数字和大于target,则输出 error
// 4. 否则输出sum和方案
int minDifference = 2147483647; // 与target的最小差
int target = -1;
int state = -1; // 状态 0->存在解决方案 1->重复 -1->无解决方案
vector<int> tempSolution; // 临时存储解决方案
vector<int> solution; // minDifference对应的解决方案
// divisor最多比num的长度多1
bool divisorInNum(int num, int divisor) {
if (num / divisor != 0) {
return true;
}
if (num / divisor == 0 && num / (divisor / 10) != 0) {
return true;
}
return false;
}
void dfs(int num, int difference) {
// 最优化剪枝
if (difference - num > minDifference) {
return;
}
// 可行性剪枝
if (difference < 0 || (difference == 0 && num != 0)) {
return;
}
if (num == 0) {
if (difference < minDifference) {
state = 0;
// 保存符合要求的解决方案
minDifference = difference;
solution = tempSolution;
} else if (difference == minDifference) {
state = 1;
}
return;
}
int divisor = 10;
while (num != 0 && divisorInNum(num, divisor)) {
int splitor = num % divisor;
tempSolution.push_back(splitor);
dfs(num / divisor, difference - splitor);
// 回溯
tempSolution.pop_back();
divisor *= 10;
}
}
int main(int argc, char *argv[]) {
int num = -1;
while (cin >> target >> num && target != 0 && num != 0) {
minDifference = 2147483647;
state = -1;
if (num == target) {
cout << num << ' ' << num << endl;
} else {
dfs(num, target);
if (state == 0) {
cout << target - minDifference;
// 倒序遍历
for (int i = solution.size() - 1; i >= 0; i--) {
cout << " " << solution[i];
}
cout << endl;
} else if (state == -1) {
cout << "error" << endl;
} else if (state == 1) {
cout << "rejected" << endl;
}
}
}
return 0;
}