Alisha’s Party—hdu5437（模拟+优先队列）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5437

题意：公主有k个朋友来参加她的生日party，每个人都会带价值为v[i]的礼物过来，在所有人到齐之前公主会打开大门m次，每次开门就是在第t个人到来之后，然后让p个人进入大厅，如果当前人数不足p人，则让所有人都进去，最后在所有人都来到门口时，再次打开门，让剩下所有的人都进入大厅；当然选择礼物价值大的先进入，如果两个人的礼物价值相等，则先来的先进，现在有q个问题，问第ni个进入大厅的人是谁；

我们可以用优先队列存入每次开门可以进去的人，然后按顺序依次进入p个人，模拟，注意细节即可；

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <math.h>using namespace std;#define met(a, b) memset(a, b, sizeof(a))
#define N 150003
#define INF 0x3f3f3f3ftypedef long long LL;struct node
{
    int Time, v;
    char Name[];
    friend bool operator < (node p, node q)
    {
        if(p.v != q.v)
            return p.v < q.v;
        return p.Time > q.Time;
    }
}a[N];struct Open
{
    int t, cnt;
    bool friend operator < (Open p, Open q)
    {
        return p.t < q.t;
    }
}b[N];int n, m, q;char ans[N][];void solve()
{
    priority_queue<node> Q;///优先队列注意优先级；    node p;    int j = , k = ;    for(int i=; i<=m; i++)
    {
        while(j <= b[i].t && j<=n)///把此次开门能进去的先放入队列；
        {
            Q.push(a[j]);
            j++;
        }
        int num = b[i].cnt;        while(!Q.empty() && num --)///每次进num个人，如果不足num就是全进入，进入大厅，即出队列；
        {
            p = Q.top();
            Q.pop();
            strcpy(ans[k++], p.Name);
        }
    }
    while(j<=n)///把剩下没有进入队列的放入队列；
    {
        Q.push(a[j]);
        j++;
    }
    while(!Q.empty())///当所有人都到了之后，再次打开门，让所有人都进去；
    {
        p = Q.top();
        Q.pop();
        strcpy(ans[k++], p.Name);
    }
}int main()
{
    int T;    scanf("%d", &T);    while(T--)
    {
        scanf("%d %d %d", &n, &m, &q);
        for(int i=; i<=n; i++)
        {
            scanf("%s %d", a[i].Name, &a[i].v);
            a[i].Time = i;
        }        for(int i=; i<=m; i++)
            scanf("%d %d", &b[i].t, &b[i].cnt);        sort(b+, b+m+);        solve();        for(int i=; i<=q; i++)
        {
            int x;
            scanf("%d", &x);
            printf("%s%c", ans[x], i==q?'\n':' ');
        }
    }
    return ;
}