What is the problem D from AtCoder Regular Contest 068 called?

本文共计816个文字，预计阅读时间需要4分钟。

链接：[atcoder-regular-contest-068-d](http://www.elijahqi.win/2017/12/22/atcoder-regular-contest-068-d/)

题目：D - Card Eater

时间限制：2秒 / 内存限制：256MB

分数：400分

问题描述：Snuke 决定玩一个使用纸牌的游戏。他有一副牌，牌的数量为 cons。他想要通过一系列操作来使牌堆变成有序的。每次操作，他可以选择两堆牌，并按照一定的规则合并它们。目标是使最终得到的牌堆有序。

输入：第一行包含一个整数 n，表示牌堆中牌的数量。第二行包含 n 个整数，表示牌堆中每张牌的顺序。

输出：输出一个整数，表示最小的操作次数，使牌堆有序。

注意：- 纸牌的顺序从 1 到 cons。- 输入数据保证可以找到一种操作顺序，使得牌堆最终有序。

(​​www.elijahqi.win/2017/12/22/atcoder-regular-contest-068-d/​​​)
D - Card Eater

Time limit : 2sec / Memory limit : 256MB

Score : 400 points
Problem Statement

Snuke has decided to play a game using cards. He has a deck consisting of N cards. On the i-th card from the top, an integer Ai is written.

He will perform the operation described below zero or more times, so that the values written on the remaining cards will be pairwise distinct. Find the maximum possible number of remaining cards. Here, N is odd, which guarantees that at least one card can be kept.

Operation: Take out three arbitrary cards from the deck. Among those three cards, eat two: one with the largest value, and another with the smallest value. Then, return the remaining one card to the deck.
Constraints

3≦N≦105
N is odd.
1≦Ai≦105
Ai is an integer.

Input

The input is given from Standard Input in the following format:

N
A1 A2 A3 … AN

Output

Print the answer.
Sample Input 1
Copy

5
1 2 1 3 7

Sample Output 1
Copy

3

One optimal solution is to perform the operation once, taking out two cards with 1 and one card with 2. One card with 1 and another with 2 will be eaten, and the remaining card with 1 will be returned to deck. Then, the values written on the remaining cards in the deck will be pairwise distinct: 1, 3 and 7.
Sample Input 2
Copy

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

Sample Output 2
Copy

7

题目要求我们求一个 最多剩下多少 那么就是我统计一下 所有种类 比1多的有多少个 如果这个和是奇数那么答案就是种类数-1 否则答案就是种类数

#include<cstdio>
#include<algorithm>
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0;char ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
return x;
}
int n,cnt[110000];
int main(){
freopen("arc.in","r",stdin);
n=read();int max1=0,x=0;for (int i=1;i<=n;++i) x=read(),max1=max(max1,x),cnt[x]++;int kind=0,sum=0;
for (int i=1;i<=max1;++i) if (cnt[i]) sum+=cnt[i]-1,kind++;
if (sum%2) kind--; printf("%d",kind);
return 0;
}