首页 > 代码库 > 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]被窃的项链