UVa 11321

題目

http://domen111.github.io/UVa-Easy-Viewer/?11321

給定一個長度為 $n$ 的序列以及一個正整數 $m$

根據以下的規則排序

• 若 $p % m < q % m$
  $p$ 排在 $q$ 前面
• 若 $p % m > q % m$
  $q$ 排在 $p$ 前面
• 若 $p % m = q % m$
  • 若 $p, q$ 皆為偶數
    小的排前面
  • 若 $p, q$ 皆為奇數
    大的排前面
  • 否則
    奇數的排前面

想法

只需要根據題目的意思自訂 compare function 即可

Code

//By Koios1143
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n, m, arr[10010];

bool cmp(int a, int b){
	if(a%m != b%m) return a%m < b%m;
	else{
		if(a%2==0 && b%2==0) return a < b;
		else if(abs(a%2)==1 && abs(b%2)==1) return a > b;
		else return abs(a%2)==1;
	}
}

int main(){
	while(cin>>n>>m && (n!=0 && m!=0)){
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		sort(arr, arr+n ,cmp);
		cout<<n<<" "<<m<<"\n";
		for(int i=0 ; i<n ; i++){
			cout<<arr[i]<<"\n";
		}
	}
	cout<<"0 0\n";
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資排序時間複雜度為 $O(nlogn)$

每筆測資輸出時間複雜度為 $O(n)$

每筆測資總時間複雜度為 $O(n + nlogn)$