回到 CPE 必考一顆星 49 題選集 程式解題通用技巧總整理

UVa 11321 - Sort! Sort!! And Sort!!!

( Tip: 點擊左上方的三橫槓選單按鈕，可以收起左側 Pdf 頁。)

Step 1. 題目概要

• 輸入測資檔包含 20 筆的輸入測資。每組測資一開始包含兩個整數 N, M。(0 ≦ N,M ≦ 10000)
• 接下來的N行裡每一行只包含一個整數。這些整數保證都可以被存在32-bit有號整處理。輸入N=0,M=0時表示結束，同時也一起輸出0 0。
• 先利用每個數字除以M的餘數由小到大排，並遵守以下規則：
  • 若排序中比較的兩數為一奇一偶且兩數除以M 的餘數相等，則奇數要排在偶數前面。
  • 若兩奇數除以M餘數大小相等，則原本數值較大的奇數排在前面。
  • 若兩偶數除以M餘數大小相等，則較小的偶數排在前面。
• 負數的餘數計算和C語言裡的定義相同，即負數的餘數絕對不會大於零。例如：-100 MOD 3 = -1, -100 MOD 4 = 0 依此類推。

Step 2. 解題思路

• 可以善用algorithm函式庫的sort函式的第三參數去做判斷。
• 判斷依據為：
  • 一奇一偶，奇數前 偶數後
  • 兩奇數，大奇前
  • 兩偶數，小偶前

Step 3. 範例輸入與輸出 - Sample Input and Output

• Sample Input
• Sample Output
• Extra Samples (人工測資)
• Useful Tools

15 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 0

15 3
15
9
3
6
12
13
7
1
4
10
11
5
2
8
14
0 0

Extra Sample Input
Extra Sample Output

uDebug 快速連結
Diffnow (線上比對程式)
C++ Online Compiler
Python Online Compiler

Step 4. 參考程式碼 - Accepted Code

• Solution 1 ( C++ )

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

int n,m;
bool cmp(int a,int b) {
    if(a%m!=b%m) return a%m<b%m; //餘數不同，餘數小的前 大的後
    else { //餘數相同
        if(abs(a%2)) {
            if(abs(b%2)) return a>b; //a奇b奇，大奇數排前面
            else return true; //a奇b偶，所以位置要互換
        } else {
            if(abs(b%2)) return false; //a偶b奇數，所以位置不用換
            else return a<b; //a偶b偶，小偶數排前面
        }
        //一奇一偶，奇數前 偶數後
        //兩奇數，大奇前
        //兩偶數，小偶前
    }
    return a<b;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    while(cin>>n>>m) {
        if(n==0 && m==0) {
            cout<<0<<" "<<0<<"\n";
            break;
        }
        cout<<n<<" "<<m<<"\n";
        int A[10005];
        for(int i=0; i<n; i++) {
            cin>>A[i];
        }

        sort(A, A+n, cmp); //對數組A的0~n-1元素進行cmp排序

        for(int i=0; i<n; i++) {
            cout<<A[i]<<"\n";
        }
    }
    return 0;
}

回到 CPE 必考一顆星 49 題選集