首页 > 代码库 > 2612. [FHZOI 2017]被窃的项链
2612. [FHZOI 2017]被窃的项链
2612. [FHZOI 2017]被窃的项链
★★★ 输入文件:stolen_necklace.in
输出文件:stolen_necklace.out
简单对比
时间限制:1 s 内存限制:256 MB
【题目描述】
Alice和Bob偷(划掉)通过某些奇技淫巧弄来了一串上面有N(N<=100000)颗宝石的项链(注意是链不是环),其中包含若干种不同的宝石。每颗宝石拥有自己的类型编号Ki(Ki<=30000)。Alice和Bob需要平分这条项链,这意味着他们需要将每种类型宝石都平分(比如有4颗类型编号为1的宝石和2颗类型编号为2的宝石,你需要给你和你的朋友各2颗1型宝石和1颗2型宝石)。显然他们可以通过将所有宝石一颗一颗裁下来并平分,不过Bob觉得这件事很无聊,他希望能通过最小的裁剪次数来实现平分。Alice和Bob都不善于数学,所以Bob想问你最小的切割次数是多少。
HOWEVER
由于Alice的脑冻过大,所以她将问题改为:如果随机打乱这条项链,保证能够平分这条项链的最小切割次数是多少?
【输入格式】
第一行为一个整数N,代表项链上的宝石数量。
接下来的一行有N个数,其中的第i个数代表第i颗宝石的类型Ki。
数据保证每种类型的宝石都有偶数个。
【输出格式】
保证能够平分项链所需的最小切割次数。
【样例输入】
10
1 2 2 5 1 3 1 5 1 3
【样例输出】
4
【提示】
针对未随机打乱的样例的一种划分方式(仅供示意划分方式):
【来源】
Albert S. Chang
False HZOI 2017
so 神奇:
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int N=100010; bool vis[N]; int ans=0; int main() { freopen("stolen_necklace.in","r",stdin); freopen("stolen_necklace.out","w",stdout); int n; cin>>n; for(int i=1;i<=n;i++) { int zhu; cin>>zhu; if(!vis[zhu]) { ans++; vis[zhu]=1; } } cout<<ans; return 0; }
2612. [FHZOI 2017]被窃的项链
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。