UVA 11321 Sort! Sort!! and Sort!!!

題目連結 UVA 11321

題目內容

Hmm! Here you are asked to do a simple sorting. You will be given N numbers and a positive integer M. You will have to sort the N numbers in ascending order of their modulo M value. If there is a tie between an odd number and an even number (that is their modulo M value is the same) then the odd number will precede the even number. If there is a tie between two odd numbers (that is their modulo M value is the same) then the larger odd number will precede the smaller odd number and if there is a tie between two even numbers (that is their modulo M value is the same) then the smaller even number will precede the larger even number.

For remainder value of negative numbers follow the rule of C programming language: A negative number can never have modulus greater than zero. E.g. -100 MOD 3 = -1, -100 MOD 4 = 0, etc.

輸入限制

The input file contains 20 sets of inputs. Each set starts with two integers N (0 < N ≤ 10000) and M (0 < M ≤ 10000) which denotes how many numbers are within this set. Each of the next N lines contains one number each. These numbers should all fit in 32-bit signed integer. Input is terminated by a line containing two zeroes.

輸出限制

For each set of input produce N + 1 lines of outputs. The first line of each set contains the value of N and M. The next N lines contain N numbers, sorted according to the rules mentioned above. Print the last two zeroes of the input file in the output file also.

解題思路

判斷依據為先輸出與m相除的餘數較小者，若相同則判斷兩者奇偶關係，若兩者皆奇則大者先輸出，若兩者皆偶則小者先輸出，若一奇一偶則先輸出奇數，最後記得輸出"0 0"。

程式碼

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool cmp(int a,int b){
    if(a%m==b%m){
        if(a&1==1 && b&1==1){
            return a>b;
        }
        else if((a&1)==0 && (b&1)==0){
            return a<b;
        }
        else{
            return a&1==1;
        }
    }
    return a%m < b%m;
}
int main(){
    while(cin>>n>>m){
        if(m==0 && n==0){
            break;
        }
        int q[n];
        memset(q,0,sizeof q);
        for(int i=0;i<n;i++){
            scanf("%d",&q[i]);
        }
        cout<<n<<" "<<m<<endl;
        sort(q,q+n,cmp);
        for(int i=0;i<n;i++){
            cout<<q[i]<<endl;
        }
    }
    cout<<"0 0"<<endl;
}

測資

Sample input

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

Sample output

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

中文題目連結 zerojudge d750