贪心构造不会

黄题绿题懵逼

横批：依托答辩

\(\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;
}