[ Google CT2004 ] RoundA : Problem C. Sorting

Problem: 
Alex and Bob are brothers and they both enjoy reading very much. They have widely different tastes on books so they keep their own books separately. However, their father thinks it is good to promote exchanges if they can put their books together. Thus he has bought an one-row bookshelf for them today and put all his sons' books on it in random order. He labeled each position of the bookshelf the owner of the corresponding book ('Alex' or 'Bob'). 

Unfortunately, Alex and Bob went outside and didn't know what their father did. When they were back, they came to realize the problem: they usually arranged their books in their own orders, but the books seem to be in a great mess on the bookshelf now. They have to sort them right now!! 

Each book has its own worth, which is represented by an integer. Books with odd values of worth belong to Alex and the books with even values of worth belong to Bob. Alex has a habit of sorting his books from the left to the right in an increasing order of worths, while Bob prefers to sort his books from the left to the right in a decreasing order of worths. 

At the same time, they do not want to change the positions of the labels, so that after they have finished sorting the books according their rules, each book's owner's name should match with the label in its position. 

Here comes the problem. A sequence of N values s0, s1, ..., sN-1 is given, which indicates the worths of the books from the left to the right on the bookshelf currently. Please help the brothers to find out the sequence of worths after sorting such that it satisfies the above description. 

Input: 
The first line of input contains a single integer T, the number of test cases. Each test case starts with a line containing an integer N, the number of books on the bookshelf. The next line contains N integers separated by spaces, representing s0, s1, ..., sN-1, which are the worths of the books. 

Output: 
For each test case, output one line containing "Case #X: ", followed by t0, t1, ..., tN-1 in order, and separated by spaces. X is the test case number (starting from 1) andt0, t1, ..., tN-1 forms the resulting sequence of worths of the books from the left to the right. 

Limits: 
1 ≤ T ≤ 30. 

Small dataset 
1 ≤ N ≤ 100 
-100 ≤ si ≤ 100 

Large dataset 
1 ≤ N ≤ 1000 
-1000 ≤ si ≤ 1000 

Sample: 

Input
2
5
5 2 4 3 1
7
-5 -12 87 2 88 20 11

Output 
Case #1: 1 4 2 3 5
Case #2: -5 88 11 20 2 -12 87

One Solution: 
問題的描述很長, 但其實是送分題 Orz... 簡單說就是給你一個數字串列, 單數使用 asc sorting order; 雙數使用 desc sorting order, 而單數與雙數在原先的數字串列位置需保留. 所以: 

原始數列: 5 2 4 3 1
排序數列: 1 4 2 3 5

上面紅色字是單數; 綠色是雙數. 經過排序後顏色的位置沒有變, 紅色由低到高排列; 綠色由高到低排列. 知道問題後代碼便是秒殺: 

view plaincopy to clipboardprint?

1. package cj2014;  
2.   
3. import java.util.Comparator;  
4. import java.util.PriorityQueue;  
5.   
6. import flib.util.io.QSReader;  
7. import flib.util.io.QSWriter;  
8.   
9. public class PC {  
10.     /** 
11.      * BD: https://code.google.com/codejam/contest/2924486/dashboard#s=p2 
12.      * @param args 
13.      */  
14.     public static void main(String args[]) throws Exception  
15.     {  
16.         String fn="C-large-practice.in";  
17.         QSReader qsr = new QSReader(String.format("data/2014/%s", fn));  
18.         QSWriter qsw = new QSWriter(String.format("data/2014/%s.out", fn));  
19.         qsr.open();       
20.         Integer pc = Integer.valueOf(qsr.line());  
21.         Comparator desCmp = new Comparator(){  
22.             @Override  
23.             public int compare(Integer o1, Integer o2) {  
24.                 return o2.compareTo(o1);  
25.             }  
26.               
27.         };  
28.         Comparator ascCmp = new Comparator(){  
29.             @Override  
30.             public int compare(Integer o1, Integer o2) {  
31.                 return o1.compareTo(o2);  
32.             }  
33.               
34.         };  
35.         System.out.printf("\t[Info] Total %d question...\n", pc);  
36.         for(int i=1; i<=pc; i++)  
37.         {  
38.             int size = Integer.valueOf(qsr.line());  
39.             System.out.printf("\t\tP%d has %d number...\n", i, size);  
40.             String ns[] = qsr.line().split(" ");  
41.             PriorityQueue alexPQ = new PriorityQueue(10, ascCmp);  
42.             PriorityQueue bobPQ = new PriorityQueue(10, desCmp);  
43.             StringBuffer strBuf = new StringBuffer();  
44.             for(int j=0; j
45.             {  
46.                 int k = Integer.valueOf(ns[j]);  
47.                 if(k%2==0) {  
48.                     bobPQ.add(k);  
49.                     ns[j]="e"; // even  
50.                 }  
51.                 else {  
52.                     alexPQ.add(k);  
53.                     ns[j]="o"; // odd  
54.                 }  
55.             }  
56.             for(int j=0; j
57.             {  
58.                 if(ns[j].equals("e")) strBuf.append(String.format("%d ", bobPQ.poll()));  
59.                 else strBuf.append(String.format("%d ", alexPQ.poll()));  
60.             }  
61.             qsw.line(String.format("Case #%d: %s", i, strBuf.toString().trim()));  
62.         }  
63.           
64.         qsr.close();  
65.         qsw.close();  
66.     }  
67. }