b680 - 百米賽道編排
題目描述
題目要求將 N 位選手（N 為 8 的倍數）按照他們的最佳成績進行分組和賽道編排。分組的規則是將選手分成 N/8 組，並按照成績排序後，以 S 型的方式分配到各組。賽道編排的規則是，在每個組內，成績越好的選手排在中間的賽道，具體順序為 45362718。
解題思路
首先，讀取所有選手的編號和最佳成績，並按照最佳成績升序排序。然後，計算出組數（N/8）。接著，按照 S 型規則將選手分配到各組。最後，按照題目要求的賽道編排順序輸出每個組的選手編號。核心思想是先排序，再按照特定規則分配和輸出。
複雜度分析
- 時間複雜度: O(n log n)，主要來自於對選手的排序。其餘操作，如分配和輸出，的時間複雜度為 O(n)。
- 空間複雜度: O(n)，主要用於儲存選手的資訊和分組後的結果。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct p{
int no;
float t;
};
bool cmp(p a,p b){
return a.t<b.t;
}
int n;
int main(){
while(cin >> n){
p play[n];
int en=n/8;
p ans[8][en];
for(int i=0;i<n;++i)
cin >> play[i].no >> play[i].t;
sort(play,play+n,cmp);
for(int i=0;i<8;++i)
for(int j=0;j<en;++j)
ans[i][j]=play[i*en+j];
for(int i=0;i<en;++i)
cout << i+1 << " " << ans[6][i].no << " " << ans[4][i].no << " " << ans[2][i].no << " " << ans[0][i].no << " " << ans[1][en-i-1].no << " " << ans[3][en-i-1].no << " " << ans[5][en-i-1].no << " " << ans[7][en-i-1].no << "\n";
}
}