题意: 有n个人进行一场自行车竞速比赛,知道了每个人第1s走fi米,以后每秒走si米,一个人扔钉子破坏比赛,每秒他都选最靠前的那个人,如果有多个人,选编号最小
的那个,问你这些人依次被破退出比赛的顺序。
分析: Si最大只有100,可以建立优先队列数组s[1..100],对于每个优先队列,按第一关键字Fi第二关键字ID排序,每次取出所有的优先队列里最大值,
然后直接 计算(Time-1)*Si + Fi 找最大的way,将对应的优先队列pop并输出对应ID即可。
#include#include #include #include #define INF 0x1f1f1f1fusing namespace std;struct node{ int fi,xu; bool operator<(const node& a)const{ return (fi a.xu); }}tt;priority_queue q[122];int main(){ int ca=1,i,j,tmp; int t,n,f,s,dmin,dmax,res; scanf("%d",&t); while(t--) { scanf("%d",&n); for(j=1;j<=n;j++) { scanf("%d%d",&f,&s); tt.fi=f; tt.xu=j; q[s].push(tt); } printf("Case #%d:\n",ca++); for(i=1;i<=n;i++) { dmax=-1; dmin=INF; for(j=1;j<=100;j++) if(!q[j].empty()) { tt=q[j].top(); if((i-1)*j+tt.fi>dmax||(i-1)*j+tt.fi==dmax&&tt.xu