iT邦幫忙

2021 iThome 鐵人賽
DAY 30
0
自我挑戰組

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

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

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

  • 分享至 

  • twitterImage
    •  

題意

  • 真．排序題
  • 輸入數字，按照要求輸出排序後的結果
  • 需要注意的有：
    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()
    • 要小心 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 篇
  1. 26
    Day 0x1A UVa10931 Parity
  2. 27
    Day 0x1B UVa10922 2 the 9s
  3. 28
    Day 0x1C UVa10420 List of Conquests
  4. 29
    Day 0x1D UVa10226 Hardwood Species
  5. 30
    Day 0x1E UVa11321 Sort! Sort!! and Sort!!!
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1123 組
團體組數
52 組
累計文章數
23096 篇
完賽人數
656 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 2018鐵人賽 javascript 2017鐵人賽 python windows php c# windows server linux css 程式設計 react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙