首页技术正文

HDU 5437 Alisha’s Party

程序员继宽技术 2022年11月11日

0 收藏 947 点赞 3,859 浏览 1440 个字

题意：有k个人带着价值v_i的礼物来，开m次门，每次在有t个人来的时候开门放进来p个人，所有人都来了之后再开一次门把剩下的人都放进来，每次带礼物价值高的人先进，价值相同先来先进，q次询问，询问第n个进来的人的名字。

解法：一道现场wa到死的模拟……拿set/map/priority_queue维护一下序列。赛后重写一遍……依旧wa到死……我只想说……

m可以为0

m可以为0啊！

orz……

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long longusing namespace std;struct node
{
    int id, val;
    char name[205];
    bool operator < (const node &tmp) const
    {
        if(val == tmp.val) return id < tmp.id;
        return val > tmp.val;
    }
}p[150005];
struct opendoor
{
    int a, b;
    bool operator < (const opendoor &tmp) const
    {
        return a < tmp.a;
    }
}od[150005];
set <node> s;
int query[105];
int main()
{
    int T;
    while(~scanf("%d", &T))
    {
        while(T--)
        {
            s.clear();
            int n, m, q;
            scanf("%d%d%d", &n, &m, &q);
            for(int i = 1; i <= n; i++)
            {
                scanf("%s%d", p[i].name, &p[i].val);
                p[i].id = i;
            }
            for(int i = 0; i < m; i++)
                scanf("%d%d", &od[i].a, &od[i].b);
            sort(od, od + m);
            int maxq;
            for(int i = 0; i < q; i++)
            {
                scanf("%d", &query[i]);
                maxq = max(maxq, query[i]);
            }
            vector <int> ans;
            int cnt = 0;
            for(int i = 1; i <= n && ans.size() < maxq; i++)
            {
                s.insert(p[i]);
                while(od[cnt].a == i && cnt < m)//要在这里判一下……因为m为0时就会使用上一个样例的输入……所以初始化一下也是可以的……
                {
                    for(int j = 0; j < od[cnt].b && !s.empty() && ans.size() < maxq; j++)
                    {
                        ans.push_back(s.begin() -> id);
                        s.erase(s.begin());
                    }
                    cnt++;
                }
            }
            while(!s.empty() && ans.size() < maxq)
            {
                ans.push_back(s.begin() -> id);
                s.erase(s.begin());
            }
            for(int i = 0; i < q; i++)
            {
                if(i) printf(" ");
                cout << p[ans[query[i] - 1]].name;
            }
            puts("");
        }
    }
    return 0;
}