水题G- CodeForces - 1051C

题目链接：https://cn.vjudge.net/problem/CodeForces-1051C

https://cn.vjudge.net/problem/1889683/origin

题目：

万圣节到了，杰哥准备给班级里的同学发糖吃，男生女生各一堆。于是他去腐败街的xx小卖部买糖，他认为糖只要是独一无二的那他就是好糖，他跟老板说他想要买n个不一样的糖，但是老板是个黑心商贩，当杰哥把糖带回去的时候才发现有挺多相同的糖
而杰哥是一个公平正直的人，他希望男生女生两堆糖中好糖的数量相同，于是他想找你帮忙来解决他的烦恼。
为了简化问题我们将不同的糖用不用的数字表示。

Input

第一行输入一个整数 n(2<=n<=100)
第二行输入n个整数 s1,s2,...sn(1<=si<=100)表示第i个糖是哪种糖

Output

如果杰哥无法将这些糖合理的分成2份则输出一行"NO"
如果可以则输出一行"YES"下一行输出n个字符，第i个字符表示第i个糖属于男生还是女生（女生输出A，男生输出B）
情况有多种，任选一种情况输出即可。

Examples

Input

4
3 5 7 1

Output

YES
BABA

Input

3
3 5 1

Output

NO

题目大意：杰哥买想买一些独一无二的好糖（只要在一堆中是唯一的就是好糖），但是老板给了他存在相同的糖，但是他要些这些糖分给两堆，使每堆的好糖都相等。

思路：只要在一堆中是唯一就是好糖，如果原来的糖果在买来的那一堆中是好糖的个数是m个，那么如果m%2=0;把好糖平分一下，不论把剩余不是好糖的糖全部分给谁都无所谓。要是如果m%2!=0,那么，你要判断一下糖果个数不为一个和两个（就是大于数目两个的糖）的糖存不存在（为什么两个不行：两个你拆开一个之后，那么另一个就变成了好糖，所以不能使好糖是数目增加），如果存在那么分一个出来，放在一堆中使他成为好糖，其余放在另一堆那他就不是就不是好糖。要是不存在个数大于两个的，那就输出“NO”。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[105];
int b[105];
int c[105];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    int w=-1;

    int m=1;
    int u=-1;
    for(int i=1; i<102; i++)
    {
        if(b[i]==1)
        {
            c[m++]=i;
        }
        if(w<b[i])
        {
            w=b[i];
            u=i;
        }
    }
    if(m%2==0&&w<3)
    {
        printf("NO\n");
    }
    else
    {
        printf("YES\n");
        for(int i=1; i<=n; i++)
        {
            int flog=0;
            for(int j=1; j<m; j++)
            {
                if(a[i]==c[j])
                {
                    flog=1;
                    if(j%2==1)
                    {
                        printf("A");
                    }
                    else
                    {
                        printf("B");
                    }
                    break;
                }
            }
            if(a[i]==u&&flog==0&&m%2==0)
            {
                flog==1;
                u=-1;
                printf("B");
            }
            else if(flog==0)
            {
                printf("A");
            }
        }
        printf("\n");
    }
    return 0;
}