南郵 OJ 1110 奇數排序

奇數排序

時間限制(普通/Java) :  2000 MS/ 6000 MS          運作記憶體限制 : 65536 KByte

總送出 : 1361            測試通過 : 355 

比賽描述

給定n個正整數，對其中的奇數按遞增次序排序。

輸入

第一行是一個正整數：測試用例數目，最多為5。之後，每個測試用例包括兩行：

l       第1行給出整數數目n，1≤n≤100000，每個整數範圍為 [0，100000)

l       第2行給出n個整數

輸出

對于每個測試用例:

l       輸出“Case #:”，#表示序号

l       輸出奇數排序後的n個整數

注意：輸出部分的結尾要求包含一個多餘的空行。

樣例輸入

2

3

4 2 1

3

3 2 1

樣例輸出

Case 1:

4 2 1

Case 2:

1 2 3

題目來源

算法與資料結構設計2009

#include<iostream>
#include<algorithm>
using namespace std;

long a[100000],b[100000],pos[100000];

int main(){
	int N,CaseNo=0;
	long n,i,j;
	cin>>N;
	while(N--){
		cin>>n;
		for(i=0,j=0;i<n;++i){
			cin>>a[i];
			if(a[i]&1){
				b[j] = a[i];
				pos[j] = i;
				++j;
			}
		}
		sort(b,b+j);
		for(i=0;i<j;++i){
			a[pos[i]] = b[i];
		}
		cout<<"Case "<<++CaseNo<<":"<<endl;
		cout<<a[0];
		for(i=1;i<n;++i){
			cout<<" "<<a[i];
		}
		cout<<endl;
	}
}