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来说一定是取最大的时候最优的，以是暴力跑就行了。

1. //冷静，冷静，冷静
2. //调不出来就重构
3. //#pragma GCC optimize(2)
4. //#pragma GCC optimize("O3")
5. #include<bits/stdc++.h>
6. #define endl '\n'
7. using namespace std;
8. typedef long long ll;
9. typedef long double ld;
10. typedef pair<ll,ll> pii;
11. const int N=1e6+10,mod=1000000007;
12. void Jiuyuan()
13. {
14.         map<ll,ll> kp;
15.         set<pii> st;
16.         ll n,m;cin>>n>>m;
17.         vector<ll> p;
18.         for(int i=1;i<=n;i++)
19.         {
20.                 ll a;cin>>a;
21.                 kp[a]++;
22.         }
23.         for(int i=1;i<=m;i++)
24.         {
25.                 ll a,b;cin>>a>>b;
26.                 if(a>b)swap(a,b);
27.                 st.insert({a,b});
28.         }
29.         vector<vector<ll>> op(n);
30.         set<ll> wyya;
31.         for(auto &v:kp)
32.         {
33.                 if(!wyya.count(v.second))p.push_back(v.second);
34.                 wyya.insert(v.second);
35.                 op[v.second].push_back(v.first);
36.         }
37.         for(auto &v:op)
38.         {
39.                 reverse(v.begin(),v.end());
40.         }
41.         ll ans=0;
42.         sort(p.begin(),p.end());
43.         for(int ii=0;ii<p.size();ii++)
44.         {
45.                 ll i=p[ii];
46.                 for(int jj=0;jj<=ii;jj++)
47.                 {
48.                         for(auto v:op[i])
49.                         {
50.                                 ll j=p[jj];
51.                                 for(auto vb:op[j])
52.                                 {
53.                                         if(v!=vb&&!st.count({min(v,vb),max(v,vb)}))
54.                                         {
55.                                                 ans=max(ans,(i+j)*(v+vb)*1ll);
56.                                                 break;
57.                                         }
58.                                 }
59.                         }
60.                 }
61.         }
62.         cout<<ans<<endl;
63. }
64. int main()
65. {
66.         ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
67.         ll T=1;
68.         cin>>T;
69.         while(T--)
70.         {
71.                 Jiuyuan();
72.         }
73.     return 0;
74. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。