hdu5437(2015 장춘 인터넷 경기 A 문제)

제목:
한 파티가 있는데 n명이 온다. 모든 사람이 선물을 가지고 온다. 선물은 가치가 있다. 방의 크기가 제한되어 있기 때문에 그는 k시간을 선택해서 문을 열고 t시간에 p사람을 들어오게 한다. 다음에 q팀에서 묻는다. 각 팀에서 숫자ni가 있는데 너로 하여금 첫 번째로 들어온 사람이 누구인지 출력하게 한다.
 
아이디어:
우선 순위 대기열을 사용하고 우선 순위를 스스로 정의하면 됩니다. 왜냐하면 cin과scanf가 우리 TLE를 한 번 혼용하는 것이 교훈이기 때문입니다.
 
코드:
 

#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int maxn = 150005;

struct PER
{
    string name;
    int pos;
    int x;
    bool operator < (const PER& rhs) const {
        if (rhs.x != x) {
            return rhs.x > x;
        }
        return rhs.pos < pos;
    }
}node[maxn];

struct E {
    int x, y;
}e[maxn];

bool cmp(E a, E b) {
    if(a.x != b.x) {
        return a.x < b.x;
    }
    return a.y < b.y;
}

priority_queue q;

string ans1[maxn];
char str[1000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,kk;
        scanf("%d%d%d",&n,&m,&kk);
        for(int i = 1; i <= n; i++) {
            scanf("%s%d",str,&node[i].x);

            node[i].name = str;
            node[i].pos = i;
        }
        for(int i = 1; i <= m; i++) {
            scanf("%d %d",&e[i].x, &e[i].y);
        }
        sort(e + 1, e + m + 1,cmp);
        while(!q.empty()) q.pop();
        int j = 1;
        int l = 1;
        for(int i = 1; i <= m; i++) {
            while(j <= e[i].x) {
                q.push(node[j]);
                j++;
            }
            //printf("%d %d
", e[i].x, e[i].y);
            for(int k = 1; k <= e[i].y;k++) {
                if(q.empty()) break;
                PER p1 = q.top(); q.pop();
                ans1[l++] = p1.name;
            //    cout << p1.name << " " << p1.x << endl;
            }
        }
        while(j <= n) {
            q.push(node[j]);
            j++;
        }
        while(!q.empty()) {
            PER p1 = q.top(); q.pop();
            ans1[l++] = p1.name;
        }
        for(int i = 1; i <= kk; i++) {
            int xx;
            scanf("%d",&xx);
            if(i == 1) printf("%s", ans1[xx].c_str());
            else printf(" %s", ans1[xx].c_str());
        }puts("");
    }
    return 0;
}