hdu5437(2015长春网络赛A题)

题意：

有一个party，会有n个人来，每个人都带着礼物来，礼物有权值，由于屋子的大小有限，所以他会选择k个时间来开门，在t时间让p个人进来，接下来有q组询问，每组询问有一个数字ni，让你输出第ni个进入的人是谁。

 

思路 ：

使用优先队列，自己定义一下优先级就好，因为cin和scanf混用我们TLE一次，这是个教训。

 

代码：

 

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<string> #include<vector>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<PER> 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\n", 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; }

 

 

 

 

 

总结

以上是生活随笔为你收集整理的hdu5437(2015长春网络赛A题)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。