CF1637E Best Pair
2026-08-14
题解
观察发现,cnt 的取值只有 n 种,考虑直接枚举 x,y 的 cnt[x],cnt[y],在这些相同的数中从大到小枚举,有解就剪枝进行下一个。
除去最大值直接匹配的情况,每次剪枝前面至少有一个不匹配对,不匹配对最多 m 个,所以总访问次数是 O(m) 的。
排序复杂度 O(nlogn),处理复杂度 O(n+m)(瓶颈在排序上)。
代码
别忘了加剪枝!!!
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 3e5+10;
struct PII {
int x , y;
bool operator< (const PII &W) const {
if(x != W.x) return x < W.x;
return y < W.y;
}
};
char *p1 , *p2 , buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF : *p1 ++)
int read() {
int x = 0 , f = 1;
char c = nc();
while(c < '0' || '9' < c) {
if(c == '-') f = -1;
c = nc();
}
while('0' <= c && c <= '9') {
x = (x<<3)+(x<<1) + c - '0';
c = nc();
}
return x*f;
}
int n , m;
int a[N];
map<int,int> cnt;
map<PII,bool> dg;
vector<int> v[N] , st;
void solve() {
n = read(); m = read();
for(int i = 1 ; i <= n ; i ++)
cnt[a[i] = read()] ++;
for(int i = 1 ; i <= m ; i ++) {
int x = read() , y = read();
if(x > y) swap(x , y);
dg[{x,y}] = true;
}
for(int i = 1 ; i <= n ; i ++)
if(cnt[a[i]]) {
if(v[cnt[a[i]]].empty()) st.push_back(cnt[a[i]]);
v[cnt[a[i]]].push_back(a[i]);
cnt[a[i]] = 0;
}
for(auto i : st)
sort(v[i].begin() , v[i].end() , greater<int>());
LL ans = 0;
for(auto xc : st) for(auto yc : st) {
if(1ll*(xc+yc)*(v[xc][0]+v[yc][0]) <= ans) continue;
for(auto x : v[xc]) for(auto y : v[yc]) {
if(1ll*(xc+yc)*(x+y) <= ans) break;
if(x == y || dg.count({min(x,y),max(x,y)})) continue;
ans = max(ans , 1ll*(xc+yc)*(x+y));
break;
}
}
printf("%lld\n" , ans);
for(auto i : st) v[i].clear();
cnt.clear(); dg.clear(); st.clear();
return;
}
int main() {
int T = read();
while(T --) solve();
return 0;
}