回到 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函式的第三參數去做判斷。
- 判斷依據為：
- 一奇一偶，奇數前 偶數後
- 兩奇數，大奇前
- 兩偶數，小偶前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 15 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 15 3
15
9
3
6
12
13
7
1
4
10
11
5
2
8
14
0 0
|
Step 4. 參考程式碼 - Accepted Code
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
35
36
37
38
39
40
41
42
43
44
| #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;
else return true;
} else {
if(abs(b%2)) return false;
else return 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);
for(int i=0; i<n; i++) {
cout<<A[i]<<"\n";
}
}
return 0;
}
|
UVa 11321 - Sort! Sort!! And Sort!!!
