A27931. 收费站在哪里在一条高速公路上，如果已知 n 座收费站的位置 x1,x2,… ,xn（不妨假设 0=x1 ≤ x2 ≤ … ≤ xn），就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是，在收集了一大堆过路费发票后，我们筛选出了 n(n-1)/2 个距离的值，现在想知道收费站都分布在哪里？当然对应一组距离值，可能有多组解，你只要输出任何一个即可。输入输入第一行给出正整数 m（< …
填空题
较难
知识点
题目描述
收费站在哪里
在一条高速公路上，如果已知 n 座收费站的位置 x1,x2,… ,xn（不妨假设 0=x1 ≤ x2 ≤ … ≤ xn），就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是，在收集了一大堆过路费发票后，我们筛选出了 n(n-1)/2 个距离的值，现在想知道收费站都分布在哪里？
当然对应一组距离值，可能有多组解，你只要输出任何一个即可。
输入
输入第一行给出正整数 m（< 50），即距离值的数量。 随后一行给出 m 个距离，均为 int 范围内的正整数。
输出
按坐标值升序列出所有收费站的位置，其中 x1=0。同行数字间以 1 个空格分隔，行首尾不得有多余空格。 注：题目保证所有坐标为 int 范围内的非负整数。
样例输入
10
3 4 6 8 1 3 5 2 4 2样例输出
0 2 4 5 8参考答案
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> x;
map<int, int> freq;
int n;
void backtrack() {
if (x.size() == n) {
for (int i = 0; i < n; ++i) {
if (i != 0) cout << " ";
cout << x[i];
}
exit(0);
}
int k = x.size();
map<int, int> current_freq = freq;
for (auto it = current_freq.begin(); it != current_freq.end(); ++it) {
int candidate = it->first;
if (candidate <= x.back()) continue;
map<int, int> temp_freq = current_freq;
bool valid = true;
for (int i = 0; i < k; ++i) {
int d = candidate - x[i];
if (temp_freq[d] <= 0) {
valid = false;
break;
}
temp_freq[d]--;
if (temp_freq[d] == 0) {
temp_freq.erase(d);
}
}
if (valid) {
x.push_back(candidate);
freq = temp_freq;
backtrack();
x.pop_back();
freq = current_freq;
}
}
}
int main() {
int m;
cin >> m;
vector<int> distances(m);
for (int i = 0; i < m; ++i) {
cin >> distances[i];
}
n = (int)((sqrt(8 * m + 1) + 1) / 2);
sort(distances.begin(), distances.end());
for (int d : distances) {
freq[d]++;
}
x.push_back(0);
backtrack();
return 0;
}
上一题
下一题