题目名称	2612. [FHZOI 2017]被窃的项链
输入输出	`stolen_necklace.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	50
题目来源	rvalue 于2017-02-19加入
开放分组	全部用户
提交状态
分类标签	构造
	分享题解

通过：24，提交：31，通过率：77.42%
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
Albert S. Chang	100	0.005 s	0.05 MiB	C++
HZOI_蒟蒻一只	100	0.015 s	0.10 MiB	C++
sxysxy	100	0.036 s	0.55 MiB	C++
_Itachi	100	0.080 s	0.32 MiB	C++
可以的.	100	0.108 s	0.31 MiB	C++
哒哒哒哒哒！	100	0.110 s	0.42 MiB	C++
rewine	100	0.123 s	1.03 MiB	C++
angel	100	0.138 s	0.40 MiB	C++
angel	100	0.147 s	0.40 MiB	C++

关于被窃的项链的近10条评论(全部评论)
回复 @FoolMike : 上bilibili搜项链分赃即可…… AntiLeaf 2017-07-12 14:25 9楼
求证代码正确性…… FoolMike 2017-06-01 21:48 8楼
全oi就这一个题是构造吗 +1s 2017-03-27 22:10 7楼
这波身败名裂。。。快读和scanf一不小心混着用的后果。。。 sxysxy 2017-02-20 20:39 6楼
这题要搞假新闻（PS:改数据坑死人qwq不过反正我也不打算放正解代码了2333333 正规题解请在B站找（我认真的 Albert S. Chang 2017-02-20 20:16 5楼
真的假的？ _Itachi 2017-02-20 18:36 4楼
这是四星题？这辣鸡贪心害我打个暴力验证了半天小一米 2017-02-20 15:44 3楼
回复 @‎Alboi_真神名��驴蛋蛋 : 您的好友【孔乙己】强势上线所以题目叫被窃的项链 Albert S. Chang 2017-02-19 18:31 2楼
读书人的事,怎么能叫偷 YGOI_真神名曰驴蛋蛋 2017-02-19 18:29 1楼

2612. [FHZOI 2017]被窃的项链

★★★ 输入文件：stolen_necklace.in 输出文件：stolen_necklace.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

Alice和Bob偷(划掉)通过某些奇技淫巧弄来了一串上面有$N$($N<=100000$)颗宝石的项链(注意是链不是环)，其中包含若干种不同的宝石。每颗宝石拥有自己的类型编号$K_i$($K_i<=30000$)。Alice和Bob需要平分这条项链，这意味着他们需要将每种类型宝石都平分(比如有4颗类型编号为1的宝石和2颗类型编号为2的宝石，你需要给你和你的朋友各2颗1型宝石和1颗2型宝石)。显然他们可以通过将所有宝石一颗一颗裁下来并平分，不过Bob觉得这件事很无聊，他希望能通过最小的裁剪次数来实现平分。Alice和Bob都不善于数学，所以Bob想问你最小的切割次数是多少。

HOWEVER

由于Alice的脑冻过大，所以她将问题改为：如果随机打乱这条项链，保证能够平分这条项链的最小切割次数是多少？

【输入格式】

第一行为一个整数$N$，代表项链上的宝石数量。

接下来的一行有$N$个数，其中的第$i$个数代表第$i$颗宝石的类型$K_i$。

数据保证每种类型的宝石都有偶数个。

【输出格式】

保证能够平分项链所需的最小切割次数。

【样例输入】

1 2 2 5 1 3 1 5 1 3

【样例输出】

【提示】

针对未随机打乱的样例的一种划分方式（仅供示意划分方式）：

【来源】

Albert S. Chang

False HZOI 2017