讯飞

算法

单纯用排序会超时，采用桶的思想，需要注意的是多种情况要满足字典序最小

#include <stdio.h>
#include <string.h>
struct ListNode{
    int value;
    int index;
    ListNode* next;
    ListNode(){
        value = 0; index = 0;
        next = NULL;
    }
};
struct List{
    int n;
    ListNode* next;
    List(){
        n = 0; next = NULL;
    }
};
const int MAXN = 1000000;
const int MAXA = 10;
int n, na, nb;
List L[MAXA];
int S[MAXN];
void Insert(List* L, int a, int i){
    ListNode* t = new ListNode();
    t->index = i;
    t->value = a;
    t->next = L[a].next;
    L[a].next = t;
    L[a].n++;
}
int main(){
    int a;
    scanf("%d%d%d", &n, &na, &nb);
    for(int i=0; i<n; i++){
        scanf("%d", &a);
        Insert(L, a, i);
    }
    int n1 = na < nb ? na : nb;
    int n2 = na + nb - n1;
    int i = MAXA;
    ListNode* p = L[i].next;
    while(n1 > 0){
        while(p && n1>0){
            if(na < nb){
                S[p->index] = 1;
            }else{
                S[p->index] = 2;
            }
            p = p->next;
            n1--;
        }
        if(n1!=0){
            i--;
            p = L[i].next;
            if(n1 < L[i].n){
                break;
            }
        }
    }
    int rn1, rn2;
    if(na < nb){
        rn1 = n1;
        rn2 = L[i].n - n1;
        while(rn2 > 0){
            S[p->index] = 2;
            rn2--;
            n2--;
            p = p->next;
        }
        while(rn1 > 0){
            S[p->index] = 1;
            rn1--;
            n1--;
            p = p->next;
        }
    }else{
        rn1 = L[i].n - n1;
        rn2 = n1;
        while(rn2 > 0){
            S[p->index] = 2;
            rn2--;
            n2--;
            p = p->next;
        }
        while(rn1>0){
            S[p->index] = 1;
            rn1--;
            n1--;
            p = p->next;
        }
    }
    while(n2>0){
        while(p && n2>0){
            if(na < nb){
                S[p->index] = 2;
            }else{
                S[p->index] = 1;
            }
            p = p->next;
            n2--;
        }
        if(n2!=0){
            i--;
            p = L[i].next;
            if(n2 < L[i].n){
                break;
            }
        }
    }
    printf("\n");
    for(int i=0; i<n; i++){
        printf("%d ", S[i]);
    }
    printf("\n");
}

5
3 2
4 4 5 4 4
1 1 2 1 2
---------------------------
5
2 3
4 4 5 4 4
1 2 1 2 2