hdu 4393 优先队列

用优先队列储存每个人的初始距离和编号,每轮求出最快的人,然后pop掉

一开始想遍历队列的,后来发现队列没办法遍历,汗-_-!

题意,给几个第一秒冲出的距离和以后速度,求每秒后最前面人的编号,求完后最前面的退出

2
3
100 1
100 2
3 100
5
1 1
2 2
3 3
4 1
3 4
Case #1:
1 3 2
Case #2:
4 5 3 2 1
Hint
The first case: 1st Second end
Player1 100m (BOOM!!)
Player2 100m
Player3 3m 2nd Second end
Player2 102m
Player3 103m (BOOM!!) 3rd Second end
Player2 104m (BOOM!!)
 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
int n,m,t;
struct node
{
int id;
int dis;
int v;
node(){}
friend bool operator<(node a,node b)
{
if(a.dis!=b.dis) return a.dis<b.dis; //距离大的先出队
else return a.id>b.id;
}
};
priority_queue<node> q[maxn];
int main()
{
int i,j,k;
//freopen("1.in","r",stdin);
scanf("%d",&t);
node qq;
int s,v,ca=;
while(t--)
{
ca++;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%d",&qq.dis,&v);
qq.id=i;
q[v].push(qq);
}
printf("Case #%d:\n",ca);
for(i=;i<n;i++)
{
int fast=-,iid=; //最快的人距离和编号
for(j=;j<=;j++)
{
if(!q[j].empty())
{
node temp=q[j].top();
if(temp.dis+i*j>fast) fast=temp.dis+i*j,iid=j;
else if(temp.dis+i*j==fast&&temp.id<q[iid].top().id)iid=j;
}
}
printf("%d",q[iid].top().id);
q[iid].pop();
if(i<n-)printf(" ");
else printf("\n");
}
}
return ;
}
上一篇:HDOJ(HDU).1412 {A} + {B} (STL SET)


下一篇:iOS 消息转发机制