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

题意

  • 真．排序题
  • 输入数字，按照要求输出排序後的结果
  • 需要注意的有：
    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++ 的怀抱)

<<:  EP16 - [TDD] 建立 Order 参数 (2/2)

>>:  从 JavaScript 角度学 Python(30) - 爬虫

Day14 Lab 2 - Object storage data层和心跳

Data层的任务主要是储存Object的component，保证资料的安全，他和API层一样也有AP...

Day 28 - 设籍有关涉及射击的射击游戏

Intro 这次是写了两个小游戏，并从里面学到一点 member function 的用法，还有字串...

[Day 27] 机器学习常犯错的十件事

机器学习常犯错的十件事 今日学习目标 探讨机器学习常犯的十件错误 前言 人工智慧近年来成为任何产业热...

Day04 - 学习 Vue CLI package.json 设定档

今天回到大神的教学 重新认识 Vue.js | Kuro Hsu 3-3 Vue CLI 环境设定与...

SQL Server Agent 权限 - 心得分享

DBABootcamp 没有 SA 权限的使用者，要如何管理 SQL Agent Jobs (作业)...