b680: 百米賽道編排

2019-08-21

內容

徑賽短中距離賽跑，皆會依照選手實力進行最佳最公平的分組及賽道，當參賽者眾多的時候，將設置預賽或複賽，分組及賽道編排時必須依循兩個原則：

實力優秀者，儘量排在中間的賽道。
實力相當者，絕對避免排在同一組。

分組及賽道編排的的方法如下：

常態分組：方法是使用 S 型的分配，比如說選手共有 31 人，每 8 人一組(因為每組要 8 個賽道) 。步驟流程可以依照下列的方法實施。
- 依照個人最佳成績排序。
- 總人數/8 = 總組數。如 31 / 8 = 4 ，必須分四組。
- 如分 4 組，每個人的分組依成績排序，設定為 123443211234…..，依照這個規則填滿為止。
賽道編排：在每個分組上面，成績越好的，越往中間集中。方法就是分組排序號，以 45362718 的順序排賽道。

輸入

第一個數字 N 代表共有幾位選手，N<= 200 ，且 N 必為 8 的倍數。
每列有兩項資料，用空白隔開 1 10.80，1 代表選手，80 是他的最佳成績。假設每一位選手的最佳成績不重複。

16
1 10.80
2 10.35
3 10.02
4 10.44
5 11.32
6 09.93
7 11.52
8 11.53
9 12.34
10 11.42
11 10.32
12 10.28
13 12.21
14 12.54
15 12.26
16 13.40

輸出

每列共有資料兩個部分，第一個資料代表分組，後面 8 筆資料代表選手所排的賽道順序。如：1 15 10 2 6 11 5 13 16，最前面的 1 代表第一組，15 10 2 6 11 5 13 16 都是選手編號，順序就是賽道的順序，最左邊為第 1 道，最右邊為第 8 道。

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

解題思路

按照最佳紀錄排序好由小到大排好
分組
- 簡單一點可以用個計數器 12344321 的往陣列丟，輸出時判斷就好但這樣效率不好，要先用一個迴圈分好組、再用兩個迴圈輸出，時間複雜度是 O(n + n²)
- 也能用數學一點的方式解，觀察規律發現他們會以每兩組數做一個循環，然後循環 4 次，第 1 組出現在每個循環中的頭和尾、2 組在頭 + 1、尾 - 1…，按照這個規律可已讓時間複雜度降至時間複雜度是 O(n)。
輸出，輸出時按照 45362718 的順序把分好組的選手排入賽道即可。

完整程式碼

AC (2ms, 100KB)

#include <stdio.h>
#include <stdlib.h>
#define MAX 210

typedef struct Node
{
    int Num;
    double Record;
}Runner;

Runner list[MAX];

int cmp(const Runner* lhs, const Runner* rhs)
{
    return lhs->Record > rhs->Record ? 1 : -1;
}

int main()
{
    int n, g, g2, g4, g6, g8;
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d %lf", &list[i].Num, &list[i].Record);
        qsort(list + 1, n, sizeof(Runner), cmp);
        g = n >> 3, g2 = g << 1, g4 = g << 2, g6 = g2 + g4, g8 = n;
        for (int i = 1; i <= g; i++)
        {
            printf("%d %d %d %d %d %d %d %d %d\n", i, list[g6 + i].Num, list[g4 + i].Num, list[g2 + i].Num, list[i].Num,
                list[g2 + 1 - i].Num, list[g4 + 1 - i].Num, list[g6 + 1 - i].Num, list[g8 + 1 - i].Num);
        }
    }
    return 0;
}