?

題目傳送門

題意：一人過生日，很多人排著隊送禮物。排隊順序是禮物價值大的優先，如果相等先來的優先。有m次開門，當t個人到了會開門讓p個人進門。最后一次讓門外的所有人按順序進門。有q次詢問，問第x個進門的人的名字。

分析：很明顯的優先隊列，首先交給隊友做，結果寫的搓，無限RE。沒辦法只能我上，因為要對字符串處理我用了string，思路正確，各種坑都解決了但是很快WA了，我的內心是奔潰的。賽后發現是cin，cout和scanf，printf沖突了?(ios::sync_with_stdio (false);關閉同步)

，以前聽說過這個問題，這次終于碰上了！解題思路是先排好序，t也是要排序的，而且有相同的t，沒到t個人來，那么入隊t個人，注意隊列中不一定有p個人，及時break，詳細見代碼。

?

代碼：

#include <cstdio> #include <iostream> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <string> using namespace std;const int N = 150000 + 10; const int INF = 0x3f3f3f3f; struct People {string name;int v, id;People () {}People (string n, int v, int id) : name (n), v (v), id (id) {}bool operator < (const People &r) const {if (v == r.v) return id > r.id;else return v < r.v;} }p[N], ans[N]; struct Op {int t, p;bool operator < (const Op &r) const {if (t == r.t) return p < r.p;else return t < r.t;} }a[N];int main(void) {ios::sync_with_stdio (false);　　　　　　　　//用了這句話，puts都不能用了int T; cin >> T;while (T--) {int n, m, q; cin >> n >> m >> q;for (int i=1; i<=n; ++i) {cin >> p[i].name >> p[i].v; p[i].id = i;}for (int i=1; i<=m; ++i) {cin >> a[i].t >> a[i].p;}sort (a+1, a+1+m);int tot = 0;priority_queue<People> Q;int n1 = 0, n2 = 1;while (!Q.empty () || n1 <= n) {while (n2 <= m && n1 == a[n2].t) {for (int i=1; i<=a[n2].p; ++i) {if (Q.empty ()) break;ans[++tot].name = Q.top ().name; Q.pop ();}n2++;}n1++;if (n1 > n) break;Q.push (People (p[n1].name, p[n1].v, p[n1].id));}while (!Q.empty ()) {ans[++tot].name = Q.top ().name; Q.pop ();}for (int x, i=1; i<=q; ++i) {cin >> x;cout << ans[x].name;if (i == q) cout << endl;else cout << " ";}}return 0; }

　　

轉載于:https://www.cnblogs.com/Running-Time/p/4806322.html

總結

以上是生活随笔為你收集整理的优先队列 HDOJ 5437 Alisha's Party的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。