首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#13209

收费站在哪里 在一条高速公路上,如果已知 n 座收费站的位置 x 1 ,x 2 ,… ,x n (不妨假设 0=x 1 ≤ x 2 ≤ … ≤ x n ),就很…

收费站在哪里

在一条高速公路上,如果已知 n 座收费站的位置 x1,x2,… ,xn(不妨假设 0=x1 ≤ x2 ≤ … ≤ xn),就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是,在收集了一大堆过路费发票后,我们筛选出了 n(n-1)/2 个距离的值,现在想知道收费站都分布在哪里?

当然对应一组距离值,可能有多组解,你只要输出任何一个即可。

时间限制:1000

内存限制:65536

输入

输入第一行给出正整数 m(< 50),即距离值的数量。 随后一行给出 m 个距离,均为 int 范围内的正整数。

输出

按坐标值升序列出所有收费站的位置,其中 x1=0。同行数字间以 1 个空格分隔,行首尾不得有多余空格。 注:题目保证所有坐标为 int 范围内的非负整数。


样例输入

10
3 4 6 8 1 3 5 2 4 2

样例输出

0 2 4 5 8
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;map&gt; #include &lt;algorithm&gt; #include &lt;cmath&gt; using namespace std; vector&lt;int&gt; x; map&lt;int, int&gt; freq; int n; void backtrack() { if (x.size() == n) { for (int i = 0; i &lt; n; ++i) { if (i != 0) cout &lt;&lt; " "; cout &lt;&lt; x[i]; } exit(0); } int k = x.size(); map&lt;int, int&gt; current_freq = freq; for (auto it = current_freq.begin(); it != current_freq.end(); ++it) { int candidate = it-&gt;first; if (candidate &lt;= x.back()) continue; map&lt;int, int&gt; temp_freq = current_freq; bool valid = true; for (int i = 0; i &lt; k; ++i) { int d = candidate - x[i]; if (temp_freq[d] &lt;= 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 &gt;&gt; m; vector&lt;int&gt; distances(m); for (int i = 0; i &lt; m; ++i) { cin &gt;&gt; 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; }</pre>
这道题暂未补解析。