P1159 排行榜【洛谷算法习题】

P1159 排行榜网页链接P1159 排行榜题目描述小迈克尔住在一个小镇上他喜欢看每周日下午发布的音乐电视评比。它每周都根据选票介绍相同的歌曲列出这些歌曲的流行排行榜。有一个星期日迈克尔和他的朋友在一起玩得太久了以致于未能看到新的流行榜。他非常失望但是不久他就发现下周至少可以部分地建立出流行榜。除了每首歌曲的位置排行榜还根据这些歌曲上周的排行列出了它们排行变动的信息更精确地说从这周起不管那首歌是继续排在原位还是排名上升或排名下降都会给出一点说明。编写程序根据给定的流行榜帮助迈克尔推断出上周可能的排行榜。输入格式第一行是一个整数N ( 1 ≤ N ≤ 100 ) N(1≤N≤100)N(1≤N≤100)表示排行榜上歌曲的总数。接下来的N NN块列出了排行信息。每块有两行组成第i块第一行是第i ii首歌曲的名称歌名包括最多不超过100 100100个英文大写字母第二行包含下列三个单词中的一个UP歌曲在排行榜上的位置上升DOWN歌曲在排行榜上的位置下滑或SAME排行不变表示与上周排行榜相比排行榜所发生的变动。输出格式N NN行输出一个上周可能的排行榜。每一行包含一首歌名即第i ii行包含排行榜上第i ii首歌的歌名。注意解不必是唯一的但对于每一个测试数据都至少有一个解。输入输出样例 #1输入 #15 HIGHHOPES UP LOWFEELINGS UP UPANDDOWN DOWN IAMSTILLSTANDING DOWN FOOLINGAROUND DOWN输出 #1UPANDDOWN IAMSTILLSTANDING FOOLINGAROUND HIGHHOPES LOWFEELINGS解题思路本题核心是贪心构造法根据本周排名与变动规则还原合法的上周排行榜。核心规则本周第i ii名标注UP表示上周排名在i ii之后DOWN表示上周排名在i ii之前SAME表示上周排名与本周一致。构造时优先固定所有SAME的歌曲在本周对应位置保证约束直接满足将DOWN类歌曲优先填入前方剩余空位UP类歌曲填入后方剩余空位严格匹配排名变动要求。题目保证至少存在一个解该贪心策略能快速构造出合法结果时间复杂度O ( n ) O(n)O(n)完美适配n ≤ 100 n≤100n≤100的数据范围。总结核心逻辑依据排名变动约束贪心构造上周排行榜固定不变项分配升降项。关键操作分类存储歌曲优先填充SAME位置DOWN填前、UP填后。效率保障线性遍历处理无复杂计算快速生成合法解。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M1e610;string s[N],c;queuelll,r;boolsa[N];intmain(){ll n;cinn;for(ll i1;in;i){cins[i]c;if(cUP)r.push(i);if(cDOWN)l.push(i);if(cSAME)sa[i]1;}for(ll i1;in;i){if(sa[i]1)couts[i]endl;else{if(!l.empty()){couts[l.front()]endl;l.pop();}elseif(!r.empty()){couts[r.front()]endl;r.pop();}}}return0;}