AtCoder Regular Contest 068-D

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≦105N is odd.1≦Ai≦105Ai 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#includeusing 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。