CF E. Best Pair

原题链接：Problem - E - Codeforces

题意：多测，每次给出n个数，m个数对。要求找到最大的f(i,j)，cnt(i)定义为i出现的次数，f(i,j)定义为(i+j)*(cnt(i)+cnt(j))，并且i和j不能是m里面出现的数对。

思路：观察可以知道所有的cnt总和是n，不同种类的cnt数量不会超过sqrt(n)的范围，那么就可以双重循环枚举cnt，时间复杂度为O(n)，如果cnt确定了，那么对于i和j来说一定是取最大的时候最优的，所以暴力跑就行了。

//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
void Jiuyuan()
{map<ll,ll> kp;set<pii> st;ll n,m;cin>>n>>m;vector<ll> p;for(int i=1;i<=n;i++){ll a;cin>>a;kp[a]++;}for(int i=1;i<=m;i++){ll a,b;cin>>a>>b;if(a>b)swap(a,b);st.insert({a,b});}vector<vector<ll>> op(n);set<ll> wyya;for(auto &v:kp){if(!wyya.count(v.second))p.push_back(v.second);wyya.insert(v.second);op[v.second].push_back(v.first);}for(auto &v:op){reverse(v.begin(),v.end());}ll ans=0;sort(p.begin(),p.end());for(int ii=0;ii<p.size();ii++){ll i=p[ii];for(int jj=0;jj<=ii;jj++){for(auto v:op[i]){ll j=p[jj];for(auto vb:op[j]){if(v!=vb&&!st.count({min(v,vb),max(v,vb)})){ans=max(ans,(i+j)*(v+vb)*1ll);break;}}}}}cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--){Jiuyuan();}return 0;
}