Day 0x1E UVa11321 Sort! Sort!! and Sort!!!

2021 iThome 鐵人賽

DAY 30

自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列第 30 篇

13th鐵人賽 uva c c++ 一顆星選集

CHA

2021-10-01 00:00:20

4891 瀏覽

分享至

題意

真．排序題
輸入數字，按照要求輸出排序後的結果
需要注意的有：
1. 重複輸入正整數 N 代表測資數和 M 直到兩者皆為 0
2. 輸出 N、M (0 0 也要輸出) 與排序後的數列
3. 排序規則
  - 按照 mod M 由小到大
  - 餘數相等則奇數在偶數前面
    - 奇數由大到小
    - 偶數由小到大
  - 負數的餘數
    - -100 MOD 3 = -1
    - -100 MOD 4 = 0

解法

用 while 迴圈輸入兩整數 N、M 並輸出，直到兩者皆為 0

while(scanf("%d %d", &N, &M)){

    printf("%d %d\n", N, M);

    if(N == 0 && M == 0){
        break;
    }
    else{
        ...
    }
}

自定義的結構存數字、餘數與奇偶，用 for 重複讀入數列並放進陣列中

typedef struct List{
    int num;
    int mod;
    int Even_Odd;
}List;

List list[10000] = {0};

for(i = 0; i < N; i++){
    scanf("%d", &list[i].num);
    list[i].mod = list[i].num % M;
    list[i].Even_Odd = abs(list[i].num % 2);
}

用 qsort 的方式加快排序與縮減程式碼

int compare(List a, List b){
    if (a.mod == b.mod) {
        if(a.Even_Odd == 0 && b.Even_Odd == 0){
            return a.num < b.num;
        }
        else if(a.Even_Odd == 1 && b.Even_Odd == 1){
            return a.num > b.num;
        }
        else if(a.Even_Odd == 1 && b.Even_Odd == 0){
            return 1;
        }
        else if(a.Even_Odd == 0 && b.Even_Odd == 1){
            return 0;
        }
    }

    return a.mod < b.mod;
}

int main(){
    ...
    qsort(list, N, sizeof(List), compare);
    ...
}

C code ver. 1

#include<stdio.h>
#include<stdlib.h>

typedef struct List{
    int num;
    int mod;
    int Even_Odd;
}List;

void swap(List *a, List *b){
    List temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int main(){

    int N, M;
    int i, j, k, temp;
    int Odd_start, Even_start, count;

    while(scanf("%d %d", &N, &M)){

        printf("%d %d\n", N, M);

        if(N == 0 && M == 0){
            break;
        }
        else{

            List list[10000] = {0};
            List sorted[10000] = {0};

            for(i = 0; i < N; i++){
                scanf("%d", &list[i].num);
                list[i].mod = list[i].num % M;
                list[i].Even_Odd = abs(list[i].num % 2);
            }

            // ascending (remainder)
            for(i = 0; i < N - 1; i++){
                for(j = i + 1; j < N; j++){
                    if(list[i].mod > list[j].mod){
                        swap(&list[i], &list[j]);
                    }
                }
            }

            Odd_start = 0;
            for(i = 0; i < N; i++){
                if(list[i].mod != list[i + 1].mod || i == N - 1){
                    // count the number of odd
                    count = 0;
                    for(j = Odd_start; j <= i; j++){
                        if(list[j].Even_Odd == 1){
                            count++;
                        }
                    }

                    // odd → even
                    Even_start = count;
                    temp = Odd_start;
                    for(j = Odd_start; j <= i; j++){
                        if(list[j].Even_Odd == 1){
                            sorted[temp] = list[j];
                            temp++;
                        }
                        else{
                            sorted[Odd_start + Even_start] = list[j];
                            Even_start++;
                        }
                    }

                    // odd ascending & even descending
                    for(j = Odd_start; j < Odd_start + count - 1; j++){
                        for(k = j + 1; k < Odd_start + count; k++){
                            if(sorted[j].num < sorted[k].num){
                                swap(&sorted[j], &sorted[k]);
                            }
                        }
                    }
                    for(j = Odd_start + count; j < i; j++){
                        for(k = j + 1; k <= i; k++){
                            if(sorted[j].num > sorted[k].num){
                                swap(&sorted[j], &sorted[k]);
                            }
                        }
                    }

                    Odd_start = i + 1;
                }
            }

            for(i = 0; i < N; i++){
                printf("%d\n", sorted[i].num);
            }
        }
    }

    return 0;
}

C code ver. 2

#include<stdio.h>
#include<stdlib.h>

typedef struct List{
    int num;
    int mod;
    int Even_Odd;
}List;

int compare(List a, List b){
    if (a.mod == b.mod) {
        if(a.Even_Odd == 0 && b.Even_Odd == 0){
            return a.num < b.num;
        }
        else if(a.Even_Odd == 1 && b.Even_Odd == 1){
            return a.num > b.num;
        }
        else if(a.Even_Odd == 1 && b.Even_Odd == 0){
            return 1;
        }
        else if(a.Even_Odd == 0 && b.Even_Odd == 1){
            return 0;
        }
    }

    return a.mod < b.mod;
}

int main(){

    int N, M;
    int i, j, k, temp;
    int Odd_start, Even_start, count;

    while(scanf("%d %d", &N, &M)){

        printf("%d %d\n", N, M);

        if(N == 0 && M == 0){
            break;
        }
        else{

            List list[10000] = {0};

            for(i = 0; i < N; i++){
                scanf("%d", &list[i].num);
                list[i].mod = list[i].num % M;
                list[i].Even_Odd = abs(list[i].num % 2);
            }

            qsort(list, N, sizeof(List), compare);

            for(i = 0; i < N; i++){
                printf("%d\n", list[i].num);
            }
        }
    }

    return 0;
}

C++

透過 Function Overloading 的特性來使用 sort()
- sort()
要小心 C / C++ 的 struct 寫法不同

#include <bits/stdc++.h>
using namespace std;

struct List{
    int num;
    int mod;
    int Even_Odd;
};

bool cmp(List a, List b){
    if(a.mod == b.mod) {
        if(a.Even_Odd == 0 && b.Even_Odd == 0){
            return a.num < b.num;
        }
        else if(a.Even_Odd == 1 && b.Even_Odd == 1){
            return a.num > b.num;
        }
        else if(a.Even_Odd == 1 && b.Even_Odd == 0){
            return true;
        }
        else{
            return false;
        }
    }

    return a.mod < b.mod;
}

int main(){

    int N, M;
    int i;
    int temp;

    while(cin >> N >> M){

        cout << N << " " << M << "\n";

        if(N == 0 && M == 0){
            break;
        }
        else{

            vector<List> v;

            for(i = 0; i < N; i++){
                cin >> temp;
                v.push_back({temp, temp % M, temp & 1});
            }

            sort(v.begin(), v.end(), cmp);

            for(auto i: v){
                cout << i.num << "\n";
            }
        }
    }

    return 0;
}

結語

先吶喊：「我終於寫完了！！！」
一開始看到教授有貼公告鼓勵大家參加，就趁著延長的暑假報看看，結果沒注意到規則【報名當天等於開賽】，沒先囤好文章的我只能記取這個教訓，就硬著頭皮寫下去了 QAQ，雖然不是什麼難度很高的文章，但沒想到也是挺耗費心神的
倒數三篇我覺得是最精華的部分 (？)，能夠明顯看出 C 與 C++ 的差異，所以故意放在壓軸，雖然好像變成在宣傳 C++ 有多讚 (的確很讚XD)
本人的程式設計能力不是很好，所以程式碼頗冗長，只是因為如果世界上某個人用 C 在解這些題目的時候，可能剛好看到這系列的文章，所以盡量寫詳細一點，希望能夠幫助到他們 (順便推薦轉投 C++ 的懷抱)