贪心构造不会
黄题绿题懵逼
横批：依托答辩
\(\text{CF1764C}\)
题目描述
有一些点，每一个点有一个点权 \(a_i\) 。你可以在任意点之间连边，最终的图需要满足不存在 \(a,b,c\) 满足 \(a_a \leqslant a_b \leqslant a_c\) 并且 \(ab,bc\) 之间有连边。
思路点拨
我们连出来的图一定可以被划分为一个二分图。不然就会存在奇环，而不论你怎么构造，奇环上就是会有一条路径不满足条件。
所以我们可以枚举一个值域的划分，假设枚举 \(w\) 这个值，那么我们让 \(a_i \leqslant w\) 的点进入左部，反之进入右部。我们最终可以让左部的每一个点都连向右部的每一个点，这样就可以满足条件。因为全部的二分图中，想要连边最多，全部的情况我们都考虑到了。
但是还存在一种极端的情况，就是划分不出来一个二分图是的左部和右部都非空，也就是说，全部的值都相等。这个时候，我们发扬人类智慧，让最终的图不存在长度为 \(2\) 的路径就可以了，所以答案就是 \(\lfloor\dfrac{n}{2} \rfloor\) 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
int T,n,a[MAXN];
signed main(){
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<n;i++)
if(a[i]!=a[i+1])
ans=max(ans,i*(n-i));
cout<<max(ans,n/2)<<endl;
}
return 0;
}