题目:click here
题意:
邀请k个朋友,每个朋友带有礼物价值不一,m次开门,每次开门让一定人数p(如果门外人数少于p,全都进去)进来,当最后所有人都到了还会再开一次门,让还没进来的人进来,每次都是礼物价值高的人先进。最后给出q个数,表示要输出第ni个进来的人的名字。
分析:
优先队列问题。注意优先队列的比较函数即出队顺序,
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm> using namespace std;
const int M = ; struct Node { // 保存来客信息
char name[];
int val;
int id;
bool operator < ( const Node x ) const { // 排序注意--在优先队列中的出队顺序
if( val == x.val ) return id > x.id;
return val < x.val;
}
}node[M];
struct Time { // 保存开门信息--要排序--给的数据可能不按顺序
int t, p;
bool operator < ( const Time x ) const { return t < x.t; }
}time[M]; int k, m, q;
char str[M][]; // 答案 void solve() {
scanf("%d%d%d", &k, &m, &q );
for( int i=; i<=k; i++ ) {
scanf("%s %d", node[i].name, &node[i].val );
node[i].id = i;
}
for( int i=; i<m; i++ )
scanf("%d%d", &time[i].t, &time[i].p );
sort( time, time+m ); // 对开门信息排序
priority_queue<Node> Q;
int order = ;
int last = ;
for( int i=; i<m; i++ ) {
int t, p; t = time[i].t; p = time[i].p;
for( int i=last+; i<=t; i++ ) {
Q.push( node[i] );
}
for( int i=; i<p; i++ ) {
if( Q.empty() ) break; // 注意当门外的人数比p小时--队列判空直接结束--否则会RE
Node nd = Q.top(); Q.pop();
order++;
strcpy( str[order], nd.name );
}
last = t;
}
for( int i=last+; i<=k; i++ ) // m次开门后还要开门一次--门外所有人都进门
Q.push( node[i] );
while( !Q.empty() ) {
Node nd = Q.top(); Q.pop();
order++;
strcpy( str[order], nd.name );
}
bool fo = false; // 输出格式
for( int i=; i<=q; i++ ) {
int s; scanf("%d", &s );
if( fo ) printf(" %s", str[s] );
else { printf("%s", str[s] ); fo = true; }
}
printf("\n");
} int main() {
int t; scanf("%d", &t );
while( t-- ) {
solve();
}
return ;
}