PAT B級(Basic Level)Practise-1015徳才論

1015.徳才論(25)
原題:
宋代の史学者司馬光は『資治通鑑』の中で有名な「徳才論」がある.
現在、受験生の徳才点数を与えています.司馬光の理論に基づいて合格順位を与えてください.
入力形式:
1行目に3つの正の整数を入力し、それぞれN(<=105)、すなわち受験生総数;L(>=60)は、最低点数ライン、すなわち徳点と才点がいずれもLを下回らない受験生を採用する資格がある.H(<100)は、優先合格ラインである徳点と才点がいずれもこのラインを下回らないものを「才徳全尽」と定義するこのような受験生は徳才の総得点によって高いものから低いものにランクされている.才能が分からないが、徳分が線に着いた受験生は「徳勝才」に属し、総点順に並べられているが、第1類の受験生の後にランクされている.徳才点はいずれもHを下回っているが、徳点が才点を下回っていない受験生は「才徳兼亡」に属しているが、まだ「徳勝才」がある者は、総得点で順位をつけているが、第2類の受験生の後にランクされている.他の最低ラインLに達した受験生も総点順だったが、3番目の受験生の後だった.
その後、N行は、各行に1人の受験生の情報を提供し、受験番号、徳分、才分を含み、そのうち受験番号は8桁の整数であり、徳才は区間[0,100]内の整数に分けられる.数字の間はスペースで区切られています.
出力フォーマット:
1行目を出力すると、まず最低スコアラインに達した受験生数Mが与えられ、その後M行が与えられ、各行は入力フォーマットに従って1人の受験生の情報が出力され、受験生は入力で説明したルールに従って高さから低までソートされる.ある種類の受験生の中で複数の人が総得点を同時にしている場合、その徳分降順に並べます.徳分も並んでいれば、受験番号の昇順で出力されます.サンプルを入力:
14 60 80 10000001 64 90 10000002 90 60 10000011 85 80 10000003 85 80 10000004 80 85 10000005 82 77 10000006 83 76 10000007 90 78 10000008 75 79 10000009 59 90 10000010 88 45 10000012 80 100 10000013 90 99 10000014 66 60
出力サンプル:
12 10000013 90 99 10000012 80 100 10000003 85 80 10000011 85 80 10000004 80 85 10000007 90 78 10000006 83 76 10000005 82 77 10000002 90 60 10000014 66 60 10000008 75 79 10000001 64 90
考え方:
この問題はまず入力データを分類し,マルチレベルソートを行う.構想ははっきりしているが,具体的な実現は煩雑である.私は純粋なC言語で実現したので、まず自分でマルチレベルのソート関数を書いてみましたが、提出した後、2つのテストノードがタイムアウトを実行していることをヒントにしました.大量のデータ入力時にソート関数の速度がさらに上がらずタイムアウトしたのではないかと疑っています.
頭が痛くてコードを変更したのか、それともタイムアウトしたのか.そこで,人が書いたC/C++ハイブリッドコードを参考にすると,この問題の多くが存在し,従来はstdlib関数ライブラリのqsortを用いてこのソート機能を実現することを提案してきた.そこで私はこの関数を学び、採用して、最終コードのオーバーチェックに成功しました.
とにかくこの問題は時間がかかったが、多くのことを学んだ.
元のコード(DIYのマルチレベルソート:タイムアウト):

#include 
#include 

struct stu
{
    int ID;
    int D;
    int C;
    int S;
};

void sort_func(struct stu* class, int num);

int main(void)
{
    int N, L, H;
    int i;
    struct stu *stud;
    struct stu *class1, *class2, *class3, *class4;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;


    scanf("%d%d%d", &N, &L, &H);
    while(N<=0)
    {
        printf("INPUT ILLEGAL!! PLEASE INPUT AGAIN!!
");
        scanf("%d%d%d", &N, &L, &H);
    }
    stud = (struct stu *)malloc(sizeof(struct stu)*N);
    class1 = (struct stu *)malloc(sizeof(struct stu)*N);
    class2 = (struct stu *)malloc(sizeof(struct stu)*N);
    class3 = (struct stu *)malloc(sizeof(struct stu)*N);
    class4 = (struct stu *)malloc(sizeof(struct stu)*N);

    for(i = 0; i < N; i++)
    {
        scanf("%d%d%d", &stud[i].ID, &stud[i].D, &stud[i].C);
        if(stud[i].Dcontinue;
        if (stud[i].D>=H && stud[i].C>=H)
        {
            class1[cnt1] = stud[i];
            class1[cnt1].S = class1[cnt1].D + class1[cnt1].C;
            cnt1++;
        }
        else if(stud[i].D>=H && stud[i].C=L)
        {
            class2[cnt2] = stud[i];
            class2[cnt2].S = class2[cnt2].D + class2[cnt2].C;
            cnt2++;
        }
        else if(stud[i].D=stud[i].C && 
            stud[i].D>=L && stud[i].C>=L)
        {
            class3[cnt3] = stud[i];
            class3[cnt3].S = class3[cnt3].D + class3[cnt3].C;
            cnt3++;
        }
        else if(stud[i].D>=L && stud[i].C>=L)
        {
            class4[cnt4] = stud[i];
            class4[cnt4].S = class4[cnt4].D + class4[cnt4].C;
            cnt4++;
        }
    }

    sort_func(class1, cnt1);
    sort_func(class2, cnt2);
    sort_func(class3, cnt3);
    sort_func(class4, cnt4);

    printf("%d
", cnt1+cnt2+cnt3+cnt4);
    for (i = 0; i < cnt1; ++i)
    {
        printf("%d %d %d", class1[i].ID, class1[i].D, class1[i].C);
        if (i!=(cnt1-1) || (cnt2+cnt3+cnt4))
        {
            printf("
");
        }
    }
    for (i = 0; i < cnt2; ++i)
    {
        printf("%d %d %d", class2[i].ID, class2[i].D, class2[i].C);
        if (i!=cnt2-1 || (cnt3+cnt4))
        {
            printf("
");
        }
    }
    for (i = 0; i < cnt3; ++i)
    {
        printf("%d %d %d", class3[i].ID, class3[i].D, class3[i].C);
        if (i!=cnt3-1 || cnt4)
        {
            printf("
");
        }
    }
    for (i = 0; i < cnt4; ++i)
    {
        printf("%d %d %d", class4[i].ID, class4[i].D, class4[i].C);
        if (i!=cnt4-1)
        {
            printf("
");
        }
    }

    free(stud);
    free(class1);
    free(class2);
    free(class3);
    free(class4);
    return 0;
}

void sort_func(struct stu *class, int num)
{
    int i, j;
    struct stu temp;

    for(i = 1; i < num; i++)
    {
        if(class[i].S>class[i-1].S)
        {
            temp = class[i];
            j = i;
            while(j>0 && class[j-1].Sclass[j] = class[j-1];
                j--;
            }
            while(j>0 && class[j-1].S==temp.S && 
                class[j-1].Dclass[j] = class[j-1];
                j--;
            }
            while(j>0 && class[j-1].S==temp.S && 
                class[j-1].D==temp.D && 
                class[j-1].ID>temp.ID)
            {
                class[j] = class[j-1];
                j--;
            }
            class[j] = temp;
        }
        else if(class[i].S==class[i-1].S)
        {
            temp = class[i];
            j = i;
            while(j>0 && class[j-1].S==temp.S && 
                class[j-1].Dclass[j] = class[j-1];
                j--;
            }
            while(j>0 && class[j-1].S==temp.S && 
                class[j-1].D==temp.D && 
                class[j-1].ID>temp.ID)
            {
                class[j] = class[j-1];
                j--;
            }
            class[j] = temp;
        }
    }
}

最終コード(ライブラリ関数を使用:正常にチェックされました)

#include 
#include 

struct stu
{
    int ID;
    int D;
    int C;
    int S;
};

int cmp(const void *p1, const void *p2)
{
    struct stu *x = (struct stu *)p1;
    struct stu *y = (struct stu *)p2;
    if (x->S!=y->S)
        return x->S < y->S;
    else if(x->D!=y->D)
        return x->D < y->D;
    else
        return x->ID > y->ID;
}

int main(void)
{
    int N, L, H;
    int i;
    struct stu *stud;
    struct stu *class1, *class2, *class3, *class4;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;


    scanf("%d%d%d", &N, &L, &H);
    while(N<=0)
    {
        printf("INPUT ILLEGAL!! PLEASE INPUT AGAIN!!
");
        scanf("%d%d%d", &N, &L, &H);
    }
    stud = (struct stu *)malloc(sizeof(struct stu)*N);
    class1 = (struct stu *)malloc(sizeof(struct stu)*N);
    class2 = (struct stu *)malloc(sizeof(struct stu)*N);
    class3 = (struct stu *)malloc(sizeof(struct stu)*N);
    class4 = (struct stu *)malloc(sizeof(struct stu)*N);

    for(i = 0; i < N; i++)
    {
        scanf("%d%d%d", &stud[i].ID, &stud[i].D, &stud[i].C);
        if(stud[i].Dcontinue;
        if (stud[i].D>=H && stud[i].C>=H)
        {
            class1[cnt1] = stud[i];
            class1[cnt1].S = class1[cnt1].D + class1[cnt1].C;
            cnt1++;
        }
        else if(stud[i].D>=H && stud[i].C=L)
        {
            class2[cnt2] = stud[i];
            class2[cnt2].S = class2[cnt2].D + class2[cnt2].C;
            cnt2++;
        }
        else if(stud[i].D=stud[i].C && 
            stud[i].D>=L && stud[i].C>=L)
        {
            class3[cnt3] = stud[i];
            class3[cnt3].S = class3[cnt3].D + class3[cnt3].C;
            cnt3++;
        }
        else if(stud[i].D>=L && stud[i].C>=L)
        {
            class4[cnt4] = stud[i];
            class4[cnt4].S = class4[cnt4].D + class4[cnt4].C;
            cnt4++;
        }
    }

    qsort(class1, cnt1, sizeof(class1[0]), cmp);
    qsort(class2, cnt2, sizeof(class2[0]), cmp);
    qsort(class3, cnt3, sizeof(class3[0]), cmp);
    qsort(class4, cnt4, sizeof(class4[0]), cmp);

    printf("%d
", cnt1+cnt2+cnt3+cnt4);
    for (i = 0; i < cnt1; ++i)
    {
        printf("%d %d %d", class1[i].ID, class1[i].D, class1[i].C);
        if (i!=(cnt1-1) || (cnt2+cnt3+cnt4))
        {
            printf("
");
        }
    }
    for (i = 0; i < cnt2; ++i)
    {
        printf("%d %d %d", class2[i].ID, class2[i].D, class2[i].C);
        if (i!=cnt2-1 || (cnt3+cnt4))
        {
            printf("
");
        }
    }
    for (i = 0; i < cnt3; ++i)
    {
        printf("%d %d %d", class3[i].ID, class3[i].D, class3[i].C);
        if (i!=cnt3-1 || cnt4)
        {
            printf("
");
        }
    }
    for (i = 0; i < cnt4; ++i)
    {
        printf("%d %d %d", class4[i].ID, class4[i].D, class4[i].C);
        if (i!=cnt4-1)
        {
            printf("
");
        }
    }

    free(stud);
    free(class1);
    free(class2);
    free(class3);
    free(class4);
    return 0;
}