http://acm.hdu.edu.cn/showproblem.php?pid=1509
裸的优先队列的应用,输入PUT的时候输入名字,值和优先值进队列,输入GRT的时候输出优先值小的名字和对应的值
注意的是优先级一样的时候输出顺序在前的
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct point {
int val,odr,num;
char na[];
bool operator <(const point & q)const
{
if (odr==q.odr) return num>q.num;
else return odr>q.odr;
}
};
int main()
{
char lsy[];
int k=;
point temp;
priority_queue<point>que;
while (~scanf("%s",lsy))
{
if (strcmp(lsy,"GET")==)
{
if (que.size()!=)
{
temp=que.top();
que.pop();
printf("%s %d\n",temp.na,temp.val);
}
else
printf("EMPTY QUEUE!\n");
}
else
{
scanf("%s %d %d",temp.na,&temp.val,&temp.odr);
temp.num=k++;
que.push(temp);
}
}
return ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1873
也很简单的优先队列,有三个医生的,每个医生又自己的顺序,所以可以建立三个队列
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct point {
int x,num;
bool operator <(const point & q)const
{
if (x==q.x) return num>q.num;
else return x<q.x;
}
};
int main()
{
int t,x,y;
char lsy[];
priority_queue<point> a,b,c;
point temp;
while (~scanf("%d",&t))
{
int k=;
while (a.size()!=)
a.pop();
while (b.size()!=)
b.pop();
while (c.size()!=)
c.pop();
while (t--)
{
scanf("%s",lsy);
if (strcmp(lsy,"IN")==)
{
scanf("%d %d",&x,&y);
temp.num=k++;
temp.x=y;
if (x==) a.push(temp);
else if (x==) b.push(temp);
else c.push(temp);
}
else
{
scanf("%d",&x);
if (x==)
{
if (a.size()==)
printf("EMPTY\n");
else
{
temp=a.top(),a.pop();
printf("%d\n",temp.num);
}
}
else if (x==)
{
if (b.size()==)
printf("EMPTY\n");
else
{
temp=b.top(),b.pop();
printf("%d\n",temp.num);
}
}
else
{
if (c.size()==)
printf("EMPTY\n");
else
{
temp=c.top(),c.pop();
printf("%d\n",temp.num);
}
}
}
}
}
return ;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1896
题意 遇到第奇数个的石头就把它往前扔规定的距离,遇到第偶数个的石头就不动它 问最远的石头据出发点(起点)的距离
优先队列的应用,想到优先队列就很好解决了
#include<cstdio>
#include<queue>
using namespace std;
struct point {
int x,y;
bool operator <(const point & q) const
{
if (x==q.x) return y>q.y;
else return x>q.x;
}
};
int main()
{
int t,n;
while (~scanf("%d",&t))
{
while (t--)
{
int k=;
priority_queue<point> que;
point temp;
scanf("%d",&n);
while (n--)
{
scanf("%d %d",&temp.x,&temp.y);
que.push(temp);
}
while (!que.empty())
{
temp=que.top(),que.pop();
if (k%==)
{
temp.x+=temp.y;
que.push(temp);
}
k++;
}
printf("%d\n",temp.x);
}
}
return ;
}