DAY 30
0

## 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++ 的懷抱)