原题链接

整数分组

思路

总体思路是根据各个数出现的次数进行划分的

首先统计各个数字出现的个数

1
2
3
4
5
6
int n,f[N],c[N];
cin>>n;
for(int i=0;i<n;i++){
    scanf("%d",&f[i]);
    c[f[i]]++;
}

根据只出现一次的数的个数(cnt)(cnt)来分类讨论

1
2
3
4
int cnt=0;//有多少个只出现了一次
for(int i=0;i<n;i++)
    if(c[f[i]]==1)
        cnt++;

  1. 出现一次的数的个数为偶数 cnt%2==0cnt\%2==0

    那么根据这些只出现一次的数进行划分

    将前cnt2\frac{cnt}{2}个只出现一次的数放在AA组里面

    后面cnt2\frac{cnt}{2}个只出现一次的数以及出现次数大于1的数均放在BB组中

1
2
3
4
5
6
7
cnt/=2;
puts("YES");
for(int i=0;i<n;i++)
   if(c[f[i]]==1&&cnt-->0)
      printf("A");//前一半个只有一次的全放在A组
   else 
      printf("B");//剩余的放在B组中

  1. 出现一次的数的个数为奇数 cnt%2==1cnt\%2==1

    分析

    如果一个数出现了两次

    将两个数分别放在两组或者放在一组都不会影响答案 (我们直接将其放在B组了)

    如果一个数出现了三次及以上

    可以将一个放在A组里剩下的全部放在BB组中

    这样该数在A组中只出现一次 在B组中出现不止一次

    分组如下

    ​ 将前⌊cnt2⌋\lfloor \frac{cnt}{2} \rfloor个只出现一次的数放在AA组里面

    ​ 将第一个出现次数大于22的数放在AA组里面

    ​ 后面⌊cnt2⌋+1\lfloor \frac{cnt}{2} \rfloor+1个只出现一次的数以及出现次数大于1的数均放在BB组中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    if(res){
        puts("YES");
        cnt/=2;
        bool flag=false;//是否以及找到第一个出现次数大于2次的数
        for(int i=0;i<n;i++)
            if(c[f[i]]==1&&cnt-->0)printf("A");//前一半个只有一次的全放在A组
        else if(!flag&&c[f[i]]>2){//第一次出现此处大于2次的数 也分在A
            printf("A");
            flag=true;
        }else printf("B");//其余放在B
    }else puts("NO");

    • 如果没有出现次数大于22次的数那么一定不会有答案 否则一定有答案

      1
      2
      3
      4
      bool res=false;
      for(int i=0;i<n;i++)
          if(c[f[i]]>2)
              res=true;

      可以将这个判断放在前面来判断是否有答案

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<unordered_set>
using namespace std;
const int N=105;
int n,f[N],c[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&f[i]);
        c[f[i]]++;
    }
    int cnt=0;//有多少个只出现了一次
    for(int i=0;i<n;i++)
        if(c[f[i]]==1)
            cnt++;
    if(cnt&1){
        bool res=false;
        for(int i=0;i<n;i++)
            if(c[f[i]]>2)
                res=true;
        if(res){
            puts("YES");
            cnt/=2;
            bool flag=false;//找到第一个出现次数大于2次的数 分一个放到A组
            for(int i=0;i<n;i++)
                if(c[f[i]]==1&&cnt-->0)printf("A");//前一半个只有一次的全放在A组
                else if(!flag&&c[f[i]]>2){
                    printf("A");//第一次出现此处大于2次的数 也分在A
                    flag=true;
                }else printf("B");//其余放在B
        }else puts("NO");
    }else{
        cnt/=2;
        puts("YES");
        for(int i=0;i<n;i++)
            if(c[f[i]]==1&&cnt-->0)printf("A");//前一半个只有一次的全放在A组
            else printf("B");
    }
    return 0;
}