【训练题解】UPC Card Eater （思维）

Problem Description

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.

Example

Sample Input 1

5

1 2 1 3 7

Sample Output 1

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

15

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

Sample Output 2

7

题意： 有一堆纸牌，牌上有对应的数字。每一次可以拿出其中三张，再将最大的和最小的丢掉，把中间的放回。要求最后剩的纸牌上的数字互不相同，问最多能剩几张牌。

思路： 当有两张相同的时，就可以选这两张和其他一种，然后仅留下一张。所以当种类数为偶数时，就会有一种牌被多选出来扔掉。

代码：

#include<bits/stdc++.h>
#define cutele main
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+7;
int st[N],n;
void solve(){
    int cnt=0;
    for(int i=0;i<N;i++) if(st[i]) cnt++;
    if(cnt%2) cout<<cnt<<endl;
    else cout<<cnt-1<<endl;
}
//思维
int cutele(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        st[x]++;
    }
    solve();
    return 0;
}