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

三元组的离心力 三元组 (a,b,c) 的“离心力”定义为 |a-b|+|b-c|+|c-a|。现给定三个非空的整数集合 S 1 、S 2 、S 3 ,请你找出…

三元组的离心力

三元组 (a,b,c) 的“离心力”定义为 |a-b|+|b-c|+|c-a|。现给定三个非空的整数集合 S1、S2、S3,请你找出所有跨这三个集合的三元组 (a,b,c)(即 a∈ S1,b∈ S2,c∈ S3)的最小离心力。

时间限制:1000

内存限制:65536

输入

输入第一行给出三个不超过 104 的正整数 n1、n2、n3,依次为集合 S1、S2、S3 中元素的个数(注意一个集合内没有相同的元素)。随后三行,顺次给出三个集合的元素,均为 [-104 , 104] 内的整数。同行数字间以空格分隔。

输出

在一行中输出 `LiXinLi(a, b, c) = d`,其中 `(a, b, c)` 是具有最小离心力的三元组,`d` 是对应的离心力。如果解不唯一,输出那个最大的解。 注意:(a1,a2,a3)>(b1,b2,b3) 是指,存在 1 ≤ k ≤ 3 使得 ai=bi 对 1 ≤ i < k 成立,并且 ak > bk。


样例输入

4 4 6
0 9 -1 11
10 -25 11 -10
9 2 41 17 12 30

样例输出

LiXinLi(11, 11, 12) = 2

提示

注意到样例实际上有两组解,另外一组解是 (9, 10, 9)。因为 (11, 11, 12) 比较大,所以输出的是这组解。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;tuple&gt; #include &lt;algorithm&gt; #include &lt;climits&gt; using namespace std; vector&lt;int&gt; find_closest(const vector&lt;int&gt;&amp; arr, int x) { vector&lt;int&gt; res; int n = arr.size(); if (n == 0) return res; auto it = lower_bound(arr.begin(), arr.end(), x); int pos = it - arr.begin(); if (pos == 0) { res.push_back(arr[0]); } else if (pos == n) { res.push_back(arr.back()); } else { int prev = arr[pos - 1]; int curr = arr[pos]; if (x - prev &lt; curr - x) { res.push_back(prev); } else if (x - prev &gt; curr - x) { res.push_back(curr); } else { res.push_back(prev); res.push_back(curr); } } return res; } int main() { int n1, n2, n3; cin &gt;&gt; n1 &gt;&gt; n2 &gt;&gt; n3; vector&lt;int&gt; S1(n1), S2(n2), S3(n3); for (int i = 0; i &lt; n1; ++i) cin &gt;&gt; S1[i]; for (int i = 0; i &lt; n2; ++i) cin &gt;&gt; S2[i]; for (int i = 0; i &lt; n3; ++i) cin &gt;&gt; S3[i]; sort(S1.begin(), S1.end()); sort(S2.begin(), S2.end()); sort(S3.begin(), S3.end()); vector&lt;tuple&lt;int, int, int&gt;&gt; candidates; // Process S1 elements for (int a : S1) { auto b_list = find_closest(S2, a); auto c_list = find_closest(S3, a); for (int b : b_list) { for (int c : c_list) { candidates.emplace_back(a, b, c); } } } // Process S2 elements for (int b : S2) { auto a_list = find_closest(S1, b); auto c_list = find_closest(S3, b); for (int a : a_list) { for (int c : c_list) { candidates.emplace_back(a, b, c); } } } // Process S3 elements for (int c : S3) { auto a_list = find_closest(S1, c); auto b_list = find_closest(S2, c); for (int a : a_list) { for (int b : b_list) { candidates.emplace_back(a, b, c); } } } int min_range = INT_MAX; for (const auto&amp; t : candidates) { int a = get&lt;0&gt;(t), b = get&lt;1&gt;(t), c = get&lt;2&gt;(t); int current_min = min({a, b, c}); int current_max = max({a, b, c}); min_range = min(min_range, current_max - current_min); } vector&lt;tuple&lt;int, int, int&gt;&gt; min_candidates; for (const auto&amp; t : candidates) { int a = get&lt;0&gt;(t), b = get&lt;1&gt;(t), c = get&lt;2&gt;(t); int current_min = min({a, b, c}); int current_max = max({a, b, c}); if (current_max - current_min == min_range) { min_candidates.push_back(t); } } tuple&lt;int, int, int&gt; best = min_candidates[0]; for (const auto&amp; t : min_candidates) { if (t &gt; best) { best = t; } } int a = get&lt;0&gt;(best), b = get&lt;1&gt;(best), c = get&lt;2&gt;(best); int d = 2 * (max({a, b, c}) - min({a, b, c})); cout &lt;&lt; "LiXinLi(" &lt;&lt; a &lt;&lt; ", " &lt;&lt; b &lt;&lt; ", " &lt;&lt; c &lt;&lt; ") = " &lt;&lt; d &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。