Morris' Blog

2011-08-21 19:27:42Morris

d750. 11321 - Sort! Sort!! and Sort!!!

留言 1 收藏 0 推薦 0

內容：

給你兩個整數 N (0<N<=10000), M (0<M<=10000)，你要依照某些規則排序N個整數。先利用每個數字除以M的餘數由小到大排，若排序中比較的兩數為一奇一偶且兩數除以 M 的餘數相等，則奇數要排在偶數前面。若兩奇數除以M餘數大小相等，則原本數值較大的奇數排在前面。同樣的，若兩偶數除以M餘數大小相等，則較小的偶數排在前面。至於負數的餘數計算和 C 語言裡的定義相同，即負數的餘數絕對不會大於零。例如 -100 MOD 3 = -1, -100 MOD 4 = 0 依此類推。

輸入說明：

輸入測資檔包含 20 筆的輸入測資。每組測資一開始包含兩個整數 N, M。接下來的 N 行裡每一行只包含一個整數。這些整數保證都可以被存在 32-bit 有號整數裡。輸入以 N=0, M=0代表結束。

輸出說明：

對於每一組輸入請輸出 N+1 行整數。第一行為兩個整數 N, M。接下來的 N 行都包含一個整數、及上述的數字按上述規則排列後的結果。對於輸入測資尾端的兩個 0, 0 請也輸出兩個空白分隔的 0, 0。

範例輸入：

範例輸出：

提示：

出處：

UVa ACM 11321 (管理：pcshic)

作法 : 自己製作 cmp 函式
題目講的優先順序, 我真的一時看不懂, 真是蠢了

/**********************************************************************************/
/* Problem: d750 "11321 - Sort! Sort!! and Sort!!!" from UVa ACM 11321           */
/* Language: C                                                                   */
/* Result: AC (6ms, 292KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-08-21 19:20:06                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
int Data[10000], X[10000], n, m, a;
int cmp(int x, int y) {
   int tx = x%m, ty = y%m;
   if((x&1) && (!(y&1))) {
       if(tx == ty)   return 1;
       return tx < ty;
   }
   if((!(x&1)) && (y&1)) {
       if(tx == ty)   return 0;
       return tx < ty;
   }
   if((x&1) && (y&1)) {
       if(tx == ty) {
           if(x > y)   return 1;
           else       return 0;
       }
       else return tx < ty;
   }
   else {
       if(tx == ty) {
           if(x < y)   return 1;
           else       return 0;
       }
       else return tx < ty;
   }
}
void Merge(int l, int m, int h) {
   int In1 = l, In2 = m+1;
   int a, b, Top = 0;
   while(In1 <= m && In2 <= h)
       if(cmp(Data[In1], Data[In2]))
           X[Top++] = Data[In1++];
       else X[Top++] = Data[In2++];
   while(In1 <= m)   X[Top++] = Data[In1++];
   while(In2 <= h) X[Top++] = Data[In2++];
   for(a = 0, b = l; a < Top; a++, b++)
       Data[b] = X[a];
}
void MergeSort(int l, int h) {
   if(l < h) {
       int m = (l+h)/2;
       MergeSort(l, m);
       MergeSort(m+1, h);
       Merge(l, m, h);
   }
}
main() {
   while(scanf("%d %d", &n, &m) == 2) {
       for(a = 0; a < n; a++)
           scanf("%d", &Data[a]);
       MergeSort(0, n-1);
       printf("%d %d\n", n, m);
       for(a = 0; a < n; a++)
           printf("%d\n", Data[a]);
       if(n == 0 && m == 0) break;
   }
   return 0;
}

上一篇：c102. Software CRC

下一篇：d781. 195 - Anagram

春藥 2020-02-20 14:01:07

很讚的分享~~

Morris' Blog

d750. 11321 - Sort! Sort!! and Sort!!!

你可能感興趣的文章

Raimundo Arrais do Rosário

柬埔寨太子集團（上）一位默默無名的中國小企業主，是如何成為坐擁億萬財富的柬國公民？

倘若

年味。(煎年糕)

台北CP值高早午餐【U&me找咖】隱藏巷弄內餐廳，台北不限時咖啡廳推薦！