XChiChiX


這不是很戲劇化的發展嗎

d750: 11321 - Sort! Sort!! and Sort!!!

  • 1483 字
  • 次閱讀
  • 則評論
  1. 1. 內容
  2. 2. 範例輸入
  3. 3. 範例輸出
  4. 4. 想法
  5. 5. 程式碼

CPE 一顆星選集 49 道必考題

題目連結:https://zerojudge.tw/ShowProblem?problemid=d750

內容

給你兩個整數 N (0 < N <= 10000), M (0 < M <= 10000)，你要依照某些規則排序N個整數。先利用每個數字除以M的餘數由小到大排，若排序中比較的兩數為一奇一偶且兩數除以M 的餘數相等，則奇數要排在偶數前面。若兩奇數除以M餘數大小相等，則原本數值較大的奇數排在前面。同樣的，若兩偶數除以M餘數大小相等，則較小的偶數排在前面。

輸入第一行有兩個整數 N, M ，接著有 N 個需排列的數。

範例輸入

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

想法

建一個 struct 分別儲存每個數的值、是否為奇數、除以 M 之餘數，接著按照題目要求排列。

程式碼

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

struct Node{
    int num;
    bool odd;
    int mod;
};
bool cmp(Node a, Node b){
    if(a.mod == b.mod){
        if(a.odd != b.odd) return a.odd;
        else if(a.odd) return a.num > b.num;
        else return a.num < b.num;
    }
    return a.mod < b.mod;
}
int main(){
    fastio;
    int N, M;
    Node node[10001];
    while(cin >> N >> M){
        cout << N << " " << M << "\n";
        if(N == 0 && M == 0) break;
        for(int i = 0; i < N; ++i){
            cin >> node[i].num;
            node[i].odd = (node[i].num & 1) ? true : false;
            node[i].mod = node[i].num % M;
        }
        sort(node, node+N, cmp);
        for(int i = 0; i < N; ++i) cout << node[i].num << "\n";
    }
    return 0;
}