Two Teams Composing CodeForces - 1335C(思维)_starlet_kiss的博客-程序员秘密

技术标签: 思维  

You have n students under your control and you have to compose exactly two teams consisting of some subset of your students. Each student had his own skill, the i-th student skill is denoted by an integer ai (different students can have the same skills).

So, about the teams. Firstly, these two teams should have the same size. Two more constraints:

The first team should consist of students with distinct skills (i.e. all skills in the first team are unique).
The second team should consist of students with the same skills (i.e. all skills in the second team are equal).
Note that it is permissible that some student of the first team has the same skill as a student of the second team.

Consider some examples (skills are given):

[1,2,3], [4,4] is not a good pair of teams because sizes should be the same;
[1,1,2], [3,3,3] is not a good pair of teams because the first team should not contain students with the same skills;
[1,2,3], [3,4,4] is not a good pair of teams because the second team should contain students with the same skills;
[1,2,3], [3,3,3] is a good pair of teams;
[5], [6] is a good pair of teams.
Your task is to find the maximum possible size x for which it is possible to compose a valid pair of teams, where each team size is x (skills in the first team needed to be unique, skills in the second team should be the same between them). A student cannot be part of more than one team.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤2⋅105) — the number of students. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤n), where ai is the skill of the i-th student. Different students can have the same skills.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n≤2⋅105).

Output
For each test case, print the answer — the maximum possible size x for which it is possible to compose a valid pair of teams, where each team size is x.

Example
Input
4
7
4 2 4 1 4 3 4
5
2 1 5 4 3
1
1
4
1 1 1 3
Output
3
1
0
2
Note
In the first test case of the example, it is possible to construct two teams of size 3: the first team is [1,2,4] and the second team is [4,4,4]. Note, that there are some other ways to construct two valid teams of size 3.
思路:我们求出一共有多少种数字x,并且求出这些数字中个数最多的一种是多少个,假设是y个。除去这一种,还剩x-1种数字。在x-1和y中取个最小值。然后如果y比x-1多2的话,说明y还可以分一个出去,那么最终答案再增加一个。
代码如下:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxx=2e5+100;
int a[maxx];
int vis[maxx];
int n;

int main()
{
    
	int t;
	scanf("%d",&t);
	while(t--)
	{
    
		scanf("%d",&n);
		for(int i=1;i<=n;i++) vis[i]=0;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]++;
		int _max=0;
		int _min=0;
		for(int i=1;i<=n;i++)
		{
    
			_max=max(_max,vis[i]);
			if(vis[i]!=0) _min++;
		}
		_min-=1;
		int ans=min(_min,_max);
		if(_max-ans>=2) ans++;
		cout<<ans<<endl;
	}
	return 0;
}

努力加油a啊,(o)/~

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/starlet_kiss/article/details/105528729

智能推荐

跨时钟域设计四之异步FIFO(附代码)_溺死在知识的海洋的博客-程序员秘密

异步FIFO二进制实现指针的问题 同步指针的影响 格雷码实现指针 空满标志的产生 代码实现1.二进制实现指针的问题由于空满标志的产生,需要比较写指针与读指针是否相等。而写指针在写时钟域下,读指针在读时钟域下,两者比较需要通过同步器进行。时钟二进制计数器实现指针,可能会导致取样错误。比如,计数器从FF跳转到00,其中每一位都发生了翻转,虽然能通过同步计数器避免亚稳态,但是仍然能...

wireshark配合jmeter测试webservice接口_全栈测试笔记的博客-程序员秘密_jmeter wireshark

1.首先,获取本地和接口的ip,以便设置过滤2.wireshark设置过滤ip.dst==192.168.0.101 and ip.src==61.147.124.120 and http3.执行py文件并捕获请求捕捉到的soap请求复制soap请求&lt;soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/s...

使用css实现无滚动条滚动+使用插件自定义滚动条样式_weixin_30457065的博客-程序员秘密

使用css实现无滚动条滚动,摘抄自:曹小萌博客使用css实现无滚动条滚动,大体思路是在div外面再套一个div。这个div设置overflow:hidden。而内容div设置overflow-x: hidden;overflow-y: scroll;然后再设置外层div的width小于内容div的width,就是用一个无滚动条的div包裹另一个有滚动条的div,从而实现隐藏滚...

op2.py源码阅读和注释以及工具拆分_IYreality的博客-程序员秘密

#!/usr/bin/env python"""OP2 source code transformation toolThis tool parses the user's original source code to producetarget-specific code to execute the user's kernel functions.This prototyp...

【X86汇编语言 从实模式到保护模式】02 编写主引导扇区代码_movYou521的博客-程序员秘密_汇编文本模式

目录1. 主引导扇区2. 在屏幕上显示文字1. 主引导扇区处理器加电或复位之后,如果硬盘是首选的启动设备,那么 RMO-BIOS 将尝试读取硬盘 0 面 0 道 1 扇区。传统上,这就是主引导扇区(Main Boot Sector,MBR)。主引导扇区数据又512字节,ROM-BIOS 将其加载到逻辑 0x0000:0x7c00 处,即物理地址 0x07c00 处。一个有效的主引导扇区,其最后两个字节是 0x55 和 0xaa。如果主引导扇区有效,ROM-BIOS 就会段间跳转 jmp 0x0000:

用户 \'IIS APPPOOL\\X\' 登录失败解决方法_dinge8714的博客-程序员秘密

你在浏览器输入网址报这样的错误2然后打开你的internet信息服务(IIS)管理器3点击“应用程序池”4在右边找到你的网站名字,右键“高级设置”5找到“进程模型”的标识6点开“标识”的下拉框,选择...

随便推点

PyQt5-图标设置和气泡提示信息_weixin_30344131的博客-程序员秘密

http://www.easyicon.net/提供了PNG、ICO、ICNS等格式的图标,可以免费下载;一、设置窗体图标 1 import sys 2 from PyQt5.QtGui import QIcon 3 from PyQt5.QtWidgets import QWidget,QApplication 4 class IconClass(QWidget):...

CocosCreator 2.x Spine动画相关方法_SlowFeather的博客-程序员秘密_cocoscreator spine

CocosCreator 2.x Spine动画播放及监听前言方法设置动画融合播放动画动画信息基础事件监听自定义帧事件监听源码前言遇到一个涉及在CocosCreator2.4中播放spine动画的问题。方法设置动画融合设置动画融合,两动画融合期间不能监听动画结束//设置动画融合,两动画融合期间不能监听动画结束this.heroSpine.setMix("idle", "run", 0.2);播放动画//播放动画this.heroSpine.setAnimation(0,"run",fa

VMare虚拟机无法识别USBkey问题_芒果黑的博客-程序员秘密

虚拟机运行的系统识别不到USBkey,只显示共享usbkey,就是windows和虚拟机系统共享,使用共享的方式操作key会出现读写权限等问题只有共享模式的情况下有直接连接的情况下正常来说会有个单独的连接,要么虚拟机系统连接,要么外部系统连接,导致这个连接没有了是由于虚拟机vmare的usb的服务停止了,导致虚拟机识别不到,启动这两个服务即可...

CList使用说明_liups的博客-程序员秘密_clist

http://blog.sina.com.cn/s/blog_70441c8e0101aiwf.htmlPS:有修订,必须加入MFC库CList是通用型的列表类,你可以存放指定的数据类型,用法如下:CList list;这样就指定了CList中存放的是CPoint类型的引用;CPtrList,CObList,CStringList都是具体的用于某种类型的

小程序:开发者工具和真机调试能请求后台数据,手机预览请求不到数据,快速解决_前端老实人的博客-程序员秘密_小程序 调试模式才能请求网络

1.第一步看配置是否跟我勾选的一样2.注意:手机扫码进入小程序后,应该打开调试模式才能请求到网络数据点开后左上角应该是开发调试,点开之后重新进入就可以请求成功数据了上面是我遇到的问题,如果还不行可以参考以下几点:wx.request请求的地址不得使用localhost,而应改成本地服务器所在的电脑IP手机和电脑(本地服务器)需要连接同一局域网(WIFI网络)...

ECshop 忘记密码,重置密码_权威小土豆的博客-程序员秘密

在password这行填入新的密码, 如:md5加密字串:0192023a7bbd73250516f069df18b500md5加密字串:0192023a7bbd73250516f069df18b500 就是密码:admin123同时要注意,把ec_sale 这行里面的数字全部删除,不然的话修改是不能成功的。

推荐文章

热门文章

相关标签