C. Doremy‘s City Construction（二分图问题）

思路：把集合划分成两部分,一部分中每个数都比另一部分小,这两部分连成一个完全二分图,这种情况是最优的,还需要特判所有数都相等的情况.

代码：

void solve(){int n;cin >> n;vector<int>a(n + 1);for(int i = 1;i <= n;i ++)cin >> a[i];sort(a.begin(),a.end());if(a[1] == a[n]){cout << n/2 << endl;return;}int ans =0;for(int i = 1;i <= n;i ++){int j = i;while(j + 1 <= n && a[j + 1] == a[i])j ++;ans = max(ans ,j * (n - j));i = j;}cout << ans << endl;
}