https://codeforces.com/contest/2061/problem/B
题目大意
给出 $n \ (4 \le n \le 2 \times 10^5)$ 条边（$1 \le a_i \le 10^8$）。问是否存在一种选法可以选出四条边，组成一个等腰梯形。正方形或长方形也可以，但不能退化。
简要题解
可以想象，大概就是要枚举一些东西。
法1
赛时写的枚举底边，这样还要找到一对腰和一个顶。
复杂度
$T$：$O(n \log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
map<int, int> cnt;
for (int i : a ) cnt[i]++;
vector<int> vi, ci;
for (auto [v, c] : cnt) {
vi.push_back(v);
ci.push_back(c);
}
int m = vi.size();
vector<int> mxr2(m);
for (int i = m - 1; i >= 0; i--) {
if (ci[i] >= 2) mxr2[i] = vi[i];
if (i < m - 1 && mxr2[i + 1]) mxr2[i] = mxr2[i + 1];
}
int mx2 = 0, mx3 = 0;
for (int i = 0; i < m; i++) {
int v = vi[i], c = ci[i];
if (c >= 4) {
cout << v << ' ' << v << ' ' << v << ' ' << v << '\n';
return;
}
// v is bot
if (c >= 1) {
if (i + 1 < m && mxr2[i + 1] && i) {
cout << vi[i - 1] << ' ' << v << ' ' << mxr2[i + 1] << ' ' << mxr2[i + 1] << '\n';
return;
}
if (mx3 && mx3 * 3 > v) {
cout << mx3 << ' ' << mx3 << ' ' << mx3 << ' ' << v << '\n';
return;
}
if (mx2 && i) {
if (mx2 == vi[i - 1] && i >= 2 && mx2 * 2 + vi[i - 2] > v) {
cout << vi[i - 2] << ' ' << mx2 << ' ' << mx2 << ' ' << v << '\n';
return;
}
if (mx2 != vi[i - 1] && mx2 * 2 + vi[i - 1] > v) {
cout << mx2 << ' ' << mx2 << ' ' << vi[i - 1] << ' ' << v << '\n';
return;
}
}
}
if (c >= 2) {
if (i + 1 < m && mxr2[i + 1]) {
cout << v << ' ' << v << ' ' << mxr2[i + 1] << ' ' << mxr2[i + 1] << '\n';
return;
}
if (mx2) {
cout << mx2 << ' ' << mx2 << ' ' << v << ' ' << v << '\n';
return;
}
}
if (c == 3) { // c == 3
if (i) {
cout << vi[i - 1] << ' ' << v << ' ' << v << ' ' << v << '\n';
return;
}
}
if (c >= 2) {
mx2 = v;
}
if (c >= 3) {
mx3 = v;
}
}
cout << "-1\n";
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
法2
直接枚举腰。好处是如果有两组 $cnt \ge 2$ 的或一组 $cnt \ge 4$，那么直接就得出答案。
于是我们只需要处理唯一的腰边。这样为了满足腰加顶边大于底边，尽量选取相邻的两组边做顶边和底边。
特别注意，腰边如果 $cnt \ge 3$ 则有可能也作为顶边或底边。以及“相邻”的两条边在腰边 $cnt = 2$ 时，可能是隔着腰边的两侧的。
1
4
1 2 2 3
这样可以写出非常不容易写错的代码。复杂度与上面的方法一致。
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
map<int, int> cnt;
for (int i : a ) cnt[i]++;
int v2 = -1, c2;
for (auto [v, c] : cnt) {
if (c >= 4) {
cout << v << ' ' << v << ' ' << v << ' ' << v << '\n';
return;
}
if (c >= 2) {
if (v2 != -1) {
cout << v2 << ' ' << v2 << ' ' << v << ' ' << v << '\n';
return;
}
v2 = v;
c2 = c;
}
}
if (v2 == -1) {
cout << "-1\n";
return;
}
if (c2 == 2) {
cnt.erase(v2);
}
int pre = -1;
for (auto [v, c] : cnt) {
if (pre == -1) {
pre = v;
continue;
}
if (pre + v2 * 2 > v) {
cout << pre << ' ' << v << ' ' << v2 << ' ' << v2 << '\n';
return;
}
pre = v;
}
cout << "-1\n";
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Kevin and Puzzle - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)