iT邦幫忙

2021 iThome 鐵人賽

DAY 30
0
自我挑戰組

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

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

題意

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

解法

  • while 迴圈輸入兩整數 NM 並輸出,直到兩者皆為 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()
    • 要小心 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++ 的懷抱)

上一篇
Day 0x1D UVa10226 Hardwood Species
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言