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++;
}
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.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;
for(int jj=0;jj<=ii;jj++)
{
for(auto v:op)
{
ll j=p;
for(auto vb:op)
{
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;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]