UVa 11224 Let‘s Swim
题目描述
在世界游泳锦标赛中，共有两个阶段：资格赛和决赛。
- 资格赛：所有选手参赛，成绩最快的888名选手晋级决赛。
- 决赛：888名选手根据资格赛名次分配泳道，再根据泳道优劣和选手原始排名决定最终名次。
Gustavo\texttt{Gustavo}Gustavo希望在资格赛中尽可能慢地游泳，同时满足两个条件：
- 进入决赛（资格赛前888名）；
- 在决赛中获得奖牌（前333名）。
你需要帮他找到最差的资格赛名次，以及对应的决赛名次。
题目细节分析
1. 资格赛排名规则
- 按照时间排序，时间短者排名靠前。
- 若时间相同，则按选手的原始排名（
rank）排序，rank数值越小表示能力越强，排名越靠前。 - Gustavo\texttt{Gustavo}Gustavo是唯一能游得比00:01:0000:01:0000:01:00更快的选手。
2. 决赛泳道分配
资格赛名次1∼81 \sim 81∼8对应的泳道编号为：
| 资格赛名次 | 泳道编号 |
|---|---|
| 111 | 444 |
| 222 | 555 |
| 333 | 333 |
| 444 | 666 |
| 555 | 222 |
| 666 | 777 |
| 777 | 111 |
| 888 | 888 |
泳道优劣顺序（从优到劣）为：
4→5→3→6→2→7→1→84 \rightarrow 5 \rightarrow 3 \rightarrow 6 \rightarrow 2 \rightarrow 7 \rightarrow 1 \rightarrow 84→5→3→6→2→7→1→8
3. 决赛胜负判定
Gustavo\texttt{Gustavo}Gustavo能战胜对手的条件（满足其一即可）：
- 他的泳道比对手更优；
- 若泳道不如对手，则他的原始排名（
rank）必须比对手更好（即数值更小）。
4. 时间输入格式
时间格式为MM:SS:DD，其中：
- MMMMMM：分钟，范围00∼0900 \sim 0900∼09
- SSSSSS：秒，范围00∼5900 \sim 5900∼59
- DDDDDD：百分秒，范围00∼9900 \sim 9900∼99
为了方便比较，将时间转换为百分秒整数：
time=MM×6000+SS×100+DD \text{time} = MM \times 6000 + SS \times 100 + DDtime=MM×6000+SS×100+DD
其中00:01:0000:01:0000:01:00对应600060006000百分秒。
解题思路
核心思想
Gustavo\texttt{Gustavo}Gustavo想要游得尽可能慢，即他的资格赛时间应尽量大，但仍满足进决赛且决赛获奖牌。
因此，我们可以枚举他的资格赛时间，从慢到快，找到第一个（也是最慢的）可行时间，即可确定最差资格赛名次。
算法步骤
步骤111：读取并排序对手数据
将所有对手按资格赛时间排序，时间相同时按rank升序。
由于Gustavo\texttt{Gustavo}Gustavo的目标是进前888，我们只需考虑最快的888名对手（如果对手总数少于888，则取全部）。
步骤222：枚举Gustavo\texttt{Gustavo}Gustavo的资格赛时间
- 初始时间：设为比第888名对手的时间慢111百分秒，即
top.back().time + 1。
此时他肯定排在第888名之后。 - 时间递减：每次将时间减少111百分秒（变快），直到最快允许时间00:01:0000:01:0000:01:00减去111百分秒（即599959995999）。
步骤333：判断资格赛排名
将Gustavo\texttt{Gustavo}Gustavo与最快的888名对手放在一起排序，找到他在其中的名次gPos（从111开始编号）。
如果gPos > 8，说明未进决赛，继续加快时间。
步骤444：模拟决赛
取排序后的前888名作为决赛选手。
- 根据Gustavo\texttt{Gustavo}Gustavo的资格赛名次
gPos分配泳道。 - 对其他777名选手逐一比较，统计他能战胜的人数
beat。 - 他的决赛名次 =
finalists.size() - beat（名次111为冠军，数值越小越好）。
步骤555：检查获奖牌条件
如果finalRank <= 3，则当前时间可行。
由于时间是从慢到快枚举，第一个可行解对应的资格赛名次就是最差的，直接输出并结束循环。
复杂度分析
- 对手排序：O(NlogN)O(N \log N)O(NlogN)，N≤1000N \leq 1000N≤1000，可忽略。
- 时间枚举：最多从第888名时间（最大09:59:99≈9∗6000+59∗100+99≈6000009:59:99 \approx 9*6000+59*100+99 \approx 6000009:59:99≈9∗6000+59∗100+99≈60000）枚举到599959995999，约5.4×1045.4 \times 10^45.4×104次。
- 每次枚举内部排序999个元素，复杂度常数极小。
整体复杂度完全可行。
代码实现
// Let's Swim// UVa ID: 11224// Verdict: Accepted// Submission Date: 2026-05-24// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structSwimmer{intrank,time;};boolcmpByTime(constSwimmer&a,constSwimmer&b){if(a.time!=b.time)returna.time<b.time;returna.rank<b.rank;}intgetLane(intqualPos){intlane[9]={0,4,5,3,6,2,7,1,8};returnlane[qualPos];}intlaneGoodness(intlane){intgoodness[9]={0,7,5,3,1,2,4,6,8};returngoodness[lane];}intfinalPosition(intgRank,intgQualPos,vector<Swimmer>&finalists){intgLane=getLane(gQualPos);intbeat=0;for(inti=0;i<8;i++){if(finalists[i].rank==gRank)continue;intoLane=getLane(i+1);if(laneGoodness(gLane)<laneGoodness(oLane)){beat++;}elseif(laneGoodness(gLane)>laneGoodness(oLane)&&gRank<finalists[i].rank){beat++;}}returnfinalists.size()-beat;}intmain(){intT;scanf("%d",&T);for(intcas=1;cas<=T;cas++){intN;scanf("%d",&N);intgRank;scanf("%d",&gRank);vector<Swimmer>opp;for(inti=0;i<N-1;i++){intr;chart[10];scanf("%d %s",&r,t);intmm,ss,dd;sscanf(t,"%02d:%02d:%02d",&mm,&ss,&dd);inttime=mm*6000+ss*100+dd;opp.push_back({r,time});}sort(opp.begin(),opp.end(),cmpByTime);vector<Swimmer>top(opp.begin(),opp.begin()+min(N-1,8));// 收集关键时间点set<int>keyTimes;for(inti=0;i<top.size();i++){keyTimes.insert(top[i].time);keyTimes.insert(top[i].time+1);if(top[i].time>0)keyTimes.insert(top[i].time-1);}vector<int>times(keyTimes.rbegin(),keyTimes.rend());// 降序（从慢到快）intbestQual=-1,bestFinal=-1;for(intgTime:times){if(gTime<0)continue;vector<Swimmer>all=top;all.push_back({gRank,gTime});sort(all.begin(),all.end(),cmpByTime);intgPos=-1;for(inti=0;i<all.size();i++){if(all[i].rank==gRank&&all[i].time==gTime){gPos=i+1;break;}}if(gPos>8)continue;vector<Swimmer>finalists;for(inti=0;i<8;i++)finalists.push_back(all[i]);intfPos=finalPosition(gRank,gPos,finalists);if(fPos<=3){bestQual=gPos;bestFinal=fPos;break;}}printf("Case #%d:\n",cas);printf("Gustavo should be #%d during the qualification to achieve position #%d in the final.\n",bestQual,bestFinal);}return0;}总结
本题的关键在于：
- 正确理解资格赛和决赛的两阶段规则；
- 将时间转换为整数便于比较和枚举；
- 利用“从慢到快枚举时间”的策略，找到最慢可行时间对应的最差资格赛名次；
- 注意平局时排名决定顺序；
- 决赛名次通过战胜人数反推。