Codeforces 1682C

问题描述

给定一个有 n n n个正整数的数组 a a a。

L I S ( a ) LIS(a) LIS(a)表示 a a a的最长单调上升子序列的长度。举个例子：

L I S ( [ 2 , 1 , 1 , 3 ] ) = 2 LIS([2,1,1,3])=2 LIS([2,1,1,3])=2

L I S ( [ 3 , 5 , 10 , 20 ] ) = 4 LIS([3,5,10,20])=4 LIS([3,5,10,20])=4

L I S ( [ 3 , 1 , 2 , 4 ] ) = 3 LIS([3,1,2,4])=3 LIS([3,1,2,4])=3

定义数组 a ′ a' a′表示原数组的逆序， a ′ = [ a n , a n − 1 , … , a 1 ] a'=[a_n,a_{n-1},\dots,a_1] a′=[an​,an−1​,…,a1​]。

数组 a a a的美丽值为 m i n ( L I S ( a ) , L I S ( a ′ ) ) min(LIS(a),LIS(a')) min(LIS(a),LIS(a′))。

你的任务是得到这个数组最优重排的情况下最大的可能的美丽值。

输入格式

有多组测试数据。第一行为一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1\le t \le 10^4) t(1≤t≤104)表示测试数据的数目。测试数据的描述如下。

第一行为一个整数 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n (1\le n \le 2 \cdot 10 ^5) n(1≤n≤2⋅105)，表示数组 a a a的长度。

第二行为 n n n个整数 a 1 , a 2 , ⋯   , a n ( 1 ≤ a i ≤ 1 0 9 ) a_1,a_2,\cdots,a_n (1 \le a_i \le 10^9) a1​,a2​,⋯,an​(1≤ai​≤109)，表示数组 a a a的元素。

保证所有测试点的 n n n之和不超过 2 ⋅ 1 0 5 2 \cdot 10 ^5 2⋅105。

输出格式

对每一个测试点，输出一个整数表示最优重排 a a a后可得到的最大可能的美丽值。

输入输出样例

输入	输出
3 3 6 6 6 6 2 5 4 5 2 4 4 1 3 2 2	1 3 2

样例解释

第一个测试点， a = [ 6 , 6 , 6 ] a=[6,6,6] a=[6,6,6]且 a ′ = [ 6 , 6 , 6 ] a'=[6,6,6] a′=[6,6,6]。 L I S ( a ) = L I S ( a ′ ) = 1 LIS(a)=LIS(a')=1 LIS(a)=LIS(a′)=1。所以美丽值为 m i n ( 1 , 1 ) = 1 min(1,1)=1 min(1,1)=1。

第二个测试点， a a a可以重排为 [ 2 , 5 , 4 , 5 , 4 , 2 ] [2,5,4,5,4,2] [2,5,4,5,4,2]。 a ′ = [ 2 , 4 , 5 , 4 , 5 , 2 ] a'=[2,4,5,4,5,2] a′=[2,4,5,4,5,2]。 L I S ( a ) = L I S ( a ′ ) = 3 LIS(a)=LIS(a')=3 LIS(a)=LIS(a′)=3。

所以美丽值为 m i n ( 3 , 3 ) = 3 min(3,3)=3 min(3,3)=3，显然是最大的可能美丽值。

第三个测试点， a a a可以重排为 [ 1 , 2 , 3 , 2 ] [1,2,3,2] [1,2,3,2]。 a ′ = [ 2 , 3 , 2 , 1 ] a'=[2,3,2,1] a′=[2,3,2,1]。 L I S ( a ) = 3 LIS(a)=3 LIS(a)=3， L I S ( a ′ ) = 2 LIS(a')=2 LIS(a′)=2。

所以美丽值为 m i n ( 3 , 2 ) = 2 min(3,2)=2 min(3,2)=2，且2是最大的可能美丽值。

题解

思路：设不同元素数目为 m m m。

易知答案尽量接近 m / 2 m/2 m/2。

如果尽量保证公共部分最大，那么让相同的元素在两个 L I S LIS LIS中都存在。

不一样的元素全部分成两半。

代码如下：

#include 
using namespace std;
int n,q[100001];
void solve()
{
	scanf("%d",&n);
	map <int,int> q;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		q[x]++;
		if(q[x]<=2) cnt++;
	}
	printf("%d\n",((cnt+1)>>1));
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}