Solution. CF1336B Xenia and Colorful Gems
Description 展开目录
给出三个正整数序列
要求在三个序列中各取一个数
Solution 展开目录
我们显然希望
为了简化问题,我们现在钦定
如果我们枚举
考虑枚举
由于我们无法知道
总复杂度
Code 展开目录
- namespace Main{
- const int N = 100005;
- int T, na, nb, nc;
- ll ans;
- vector<int> a, b, c;
- LL s(int x) { return 1ll * x * x; }
- void solve(vector<int> a, vector<int> b, vector<int> c){
- for(ri i = 0, j = 0, k = 0; i < b.size(); i++){
- while(j < a.size() - 1 && a[j + 1] <= b[i]) j++;
- while(k < c.size() - 1 && c[k] < b[i]) k++;
- if(a[j] > b[i] || c[k] < b[i]) continue;
- ans = min(ans, s(b[i]-a[j]) + s(c[k]-b[i]) + s(c[k]-a[j]));
- }
- }
- void Main(){
- input(T);
- while(T--){
- input(na, nb, nc);
- a.resize(na), b.resize(nb), c.resize(nc);
- for(ri i = 0; i < na; i++) input(a[i]);
- for(ri i = 0; i < nb; i++) input(b[i]);
- for(ri i = 0; i < nc; i++) input(c[i]);
- sort(a.begin(), a.end());
- sort(b.begin(), b.end());
- sort(c.begin(), c.end());
- ans = 9e18;
- solve(a, b, c), solve(a, c, b);
- solve(b, a, c), solve(b, c, a);
- solve(c, a, b), solve(c, b, a);
- write(ans), puts("");
- }
- return;
- }
- } // namespace
本作品采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可。