AtCoder Beginner Contest 053

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

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

题目大意：

给你N个卡片，每次操作可以任意拿三个卡片出来，去掉最大值和最小值的卡片，中间值卡片放回去。

问最多可以剩余几张卡片，并且使得不重复。

重复的序列，难道你没有点想法吗？

大佬的思考：序列中一直抽重复的直接去掉，最后变成变成一个012的序列，对于2的序列，只要有两个2的序列，我就可以变成两个1，这样最后判断是否有2剩余即可

这样就解释了最优的结构，我们知道最优结构就是看是否余2，换而言之，就是判断序列不重复个数是奇数还是偶数.偶数一定需要删除一个

#include<iostream>

#include<string.h>

#include<algorithm>

#include<map>

#include<stdio.h>

using namespace std;

int main(){

  int tmp;

  int n;

  while(~scanf("%d",&n)){

    map<int,int> a;

    for (int i=1;i<=n;i++){

        scanf("%d",&tmp);

        a[tmp]++;

    }

    int k=a.size();

    if (k%2==1)printf("%d\n",k);

    else printf("%d\n",k-1);

  }

  return 0;

}

巴特西

AtCoder Beginner Contest 053

D - Card Eater

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

最新文章

热门文章