題目：click here

題意：

　　邀請k個朋友，每個朋友帶有禮物價值不一，m次開門，每次開門讓一定人數p（如果門外人數少于p，全都進去）進來，當最后所有人都到了還會再開一次門，讓還沒進來的人進來，每次都是禮物價值高的人先進。最后給出q個數，表示要輸出第ni個進來的人的名字。

分析：

　　優先隊列問題。注意優先隊列的比較函數即出隊順序，

1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 const int M = 150005; 9 10 struct Node { // 保存來客信息 11 char name[205]; 12 int val; 13 int id; 14 bool operator < ( const Node x ) const { // 排序注意--在優先隊列中的出隊順序 15 if( val == x.val ) return id > x.id; 16 return val < x.val; 17 } 18 }node[M]; 19 struct Time { // 保存開門信息--要排序--給的數據可能不按順序 20 int t, p; 21 bool operator < ( const Time x ) const { return t < x.t; } 22 }time[M]; 23 24 int k, m, q; 25 char str[M][205]; // 答案 26 27 void solve() { 28 scanf("%d%d%d", &k, &m, &q ); 29 for( int i=1; i<=k; i++ ) { 30 scanf("%s %d", node[i].name, &node[i].val ); 31 node[i].id = i; 32 } 33 for( int i=0; i<m; i++ ) 34 scanf("%d%d", &time[i].t, &time[i].p ); 35 sort( time, time+m ); // 對開門信息排序 36 priority_queue<Node> Q; 37 int order = 0; 38 int last = 0; 39 for( int i=0; i<m; i++ ) { 40 int t, p; t = time[i].t; p = time[i].p; 41 for( int i=last+1; i<=t; i++ ) { 42 Q.push( node[i] ); 43 } 44 for( int i=0; i<p; i++ ) { 45 if( Q.empty() ) break; // 注意當門外的人數比p小時--隊列判空直接結束--否則會RE 46 Node nd = Q.top(); Q.pop(); 47 order++; 48 strcpy( str[order], nd.name ); 49 } 50 last = t; 51 } 52 for( int i=last+1; i<=k; i++ ) // m次開門后還要開門一次--門外所有人都進門 53 Q.push( node[i] ); 54 while( !Q.empty() ) { 55 Node nd = Q.top(); Q.pop(); 56 order++; 57 strcpy( str[order], nd.name ); 58 } 59 bool fo = false; // 輸出格式 60 for( int i=1; i<=q; i++ ) { 61 int s; scanf("%d", &s ); 62 if( fo ) printf(" %s", str[s] ); 63 else { printf("%s", str[s] ); fo = true; } 64 } 65 printf("\n"); 66 } 67 68 int main() { 69 int t; scanf("%d", &t ); 70 while( t-- ) { 71 solve(); 72 } 73 return 0; 74 }

?

轉載于:https://www.cnblogs.com/TaoTaoCome/p/4806837.html

總結

以上是生活随笔為你收集整理的HDU OJ 5437 Alisha’s Party 2015online A的全部內容，希望文章能夠幫你解決所遇到的問題。

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