本文共 2238 字，大约阅读时间需要 7 分钟。
#include#include #include #include #include #include using namespace std;const int k_max = 150000 + 5;const int m_max = 150000 + 5;const int q_max = 100 + 5;struct node1{ char name[205]; //记录姓名 int number; //记录进入顺序编号 int value; //记录礼物的价值 bool operator < (const node1 Next) const //优先队列的 优先级定义（和以前sort定义不同） { if(value == Next.value) return number > Next.number; else return value < Next.value; }} Friend[k_max];struct node2{ int open, amount; //记录在第几个人时开门 记录开门允许进来的人数 bool operator < (const node2 Next) const //sort排序定义 { return open < Next.open; }} door[m_max];int T, k, m, q;int query[q_max]; //记录查询的位置char ans[k_max][205]; //按顺序记录弹出的人名void party(){ priority_queue process; //定义优先队列 int pos = 0; //pos跟着ans[]移动 int cnt = 0; //cnt跟着Fiend[]移动 for(int i = 0; i < m; i ++) { for(; Friend[cnt].number <= door[i].open; cnt ++) //Fiend编号 需小于 开门时的号码 process.push(Friend[cnt]); //让此时门外等着的人入队列 for(int j = 0; j < door[i].amount; j ++) //接下来就是模拟 door[i].amount个人 允许进门 { if(process.empty()) break; // 注意当门外的人数比amount小时--队列判空直接结束--否则会RE node1 temp = process.top(); process.pop(); //元素弹出 表示让他进门 strcpy(ans[pos], temp.name); //顺序记录进来的人名 pos ++; } } for(; cnt < k; cnt ++) //最后一次开门 让没进来的人全进来 process.push(Friend[cnt]); while(!process.empty()) //与上面相同 { node1 temp = process.top(); process.pop(); strcpy(ans[pos], temp.name); pos ++; }}int main(){ scanf("%d", & T); while(T --) { scanf("%d %d %d", & k, & m, & q); for(int i = 0; i < k; i ++) { scanf("%s %d", Friend[i].name, & Friend[i].value); Friend[i].number = i + 1; } for(int i = 0; i < m; i ++) scanf("%d %d", & door[i].open, & door[i].amount); sort(door, door + m); //必须对开门信息排序 party(); for(int i = 0; i < q; i ++) scanf("%d", & query[i]); for(int i = 0; i < q - 1; i ++) printf("%s ", ans[query[i] - 1]); //ans 是从 下标 0 开始 printf("%s\n", ans[query[q - 1] - 1]); } return 0;}
：
(摘自 TaoTaoCome) 邀请k个朋友，每个朋友带有礼物价值不一，m次开门，每次开门让一定人数p（如果门外人数少于p，全都进去）进来，当最后所有人都到了还会再开一次门，让还没进来的人进来，每次都是礼物价值高的人先进。最后给出q个数，表示要输出第ni个进来的人的名字。
题解：
其实就是用优先队列。RE无数次。只因为 ans的数组开小了。我开成了q_max，应该是k_max。因为ans记录的是所有的进门人k个数据（最大是150000），之后query查询其中的q（最大是100）次而已，ans需全记录。还有就是这道题需要注意 必须对 开门door 按开门时间从小到大进行排序，因为题目并没有说按顺序（坑）。优先队列 在 struct的重载 和以前的不同。
转载地址：http://rctpi.baihongyu.com/