简答题
偏难
#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 <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>
using namespace std;
vector<int> find_closest(const vector<int>& arr, int x) {
vector<int> 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 < curr - x) {
res.push_back(prev);
} else if (x - prev > curr - x) {
res.push_back(curr);
} else {
res.push_back(prev);
res.push_back(curr);
}
}
return res;
}
int main() {
int n1, n2, n3;
cin >> n1 >> n2 >> n3;
vector<int> S1(n1), S2(n2), S3(n3);
for (int i = 0; i < n1; ++i) cin >> S1[i];
for (int i = 0; i < n2; ++i) cin >> S2[i];
for (int i = 0; i < n3; ++i) cin >> S3[i];
sort(S1.begin(), S1.end());
sort(S2.begin(), S2.end());
sort(S3.begin(), S3.end());
vector<tuple<int, int, int>> 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& t : candidates) {
int a = get<0>(t), b = get<1>(t), c = get<2>(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<tuple<int, int, int>> min_candidates;
for (const auto& t : candidates) {
int a = get<0>(t), b = get<1>(t), c = get<2>(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<int, int, int> best = min_candidates[0];
for (const auto& t : min_candidates) {
if (t > best) {
best = t;
}
}
int a = get<0>(best), b = get<1>(best), c = get<2>(best);
int d = 2 * (max({a, b, c}) - min({a, b, c}));
cout << "LiXinLi(" << a << ", " << b << ", " << c << ") = " << d << endl;
return 0;
}</pre>
这道题暂未补解析。