【题解】Codeforces Global Round 19, E. Best Pair
E
You are given an array \(a\) of length \(n\). Let cntx be the number of elements from the array which are equal to \(x\). Let's also define \(f(x,y)\) as \((cnt_x+cnt_y)?(x+y)\).
Also you are given \(m\) bad pairs \((x_i,y_i)\). Note that if \((x,y)\) is a bad pair, then \((y,x)\) is also bad.
Your task is to find the maximum value of \(f(u,v)\) over all pairs \((u,v)\), such that \(u≠v\), that this pair is not bad, and also that \(u\) and \(v\) each occur in the array \(a\). It is guaranteed that such a pair exists.
枚举题,但是我并不熟悉这种复杂度的分析
第一想法是用堆维护,但是这种题并不能对所有数对构造一个比较直接的划分和次序关系
考虑枚举,对于式子 \((cnt_x+cnt_y)?(x+y)\),我们考虑固定 x(和对应的 \(cnt_x\) ),我们再考虑枚举 y(显然复杂度会炸) \(cnt_y\)(枚举剪枝,我们只需枚举\(1\text{~} cnt_x\)),我们希望这下能快速依次得到从大到小的对应 y,我们开个vector存对应的数即可
设vector
分析复杂度,对于某个数字 x,我们枚举所有 \(c≤cnt_x\) 的 cnt 数组,总的是 O(n) 的
为什么?我们这么想,对于每个 cnt[c],我们在其中枚举了 cnt[c].size 个 x,对于每个 x 又枚举了 c 次,总的即 \(\sum{c*cnt[c].size} = n\)
每次枚举我们只需取出vector头的那个 y 即可,但是如果遇到 bad pair 我们还得继续在这个vector里取下一个,但是这么做的次数不超过 m,所以总的就是 \(O((n+m)logm+nlogn)\)
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 300005;
typedef long long ll;
int T, N, M, A[MAXN];
set map;
vector cnt[MAXN];
ll has(ll x, ll y)
{
if (x> y) x ^= y ^= x ^= y; return x*2000000000+y;
}
int cmp(int x, int y) { return x > y; }
int main()
{
for (scanf("%d", &T); T; T--) {
scanf("%d%d", &N, &M);
for (int i=1; i<=N; i++) scanf("%d", &A[i]);
map.clear();
for (int i=1; i<=M; i++) {
int a, b; scanf("%d%d", &a, &b);
map.insert(has(a, b));
}
sort(A+1, A+N+1);
for (int i=1; i<=N; i++) cnt[i].clear();
for (int p=1; p<=N;) {
int a = A[p], c = 1; p++;
while (p<=N && A[p]==a) p++, c++;
cnt[c].push_back(a);
}
for (int i=1; i<=N; i++) sort(cnt[i].begin(), cnt[i].end(), cmp);
ll ans = 0; int x, y;
for (int c=1; c<=N; c++) {
int sz = cnt[c].size();
for (int i=0; i< sz; i++) {
x = cnt[c][i];
for (int _c=1; _c<=c; _c++) {
int _sz = cnt[_c].size();
for (int j=0; j< _sz; j++) {
y = cnt[_c][j];
if (x!=y && map.find(has(x, y))==map.end()) {
ans = max(ans, 1ll*(c+_c)*(x+y));
break;
}
}
}
}
}
printf("%lld\n", ans);
}
}