排行榜"/>
洛谷P1159 排行榜
题面:
样例输入#1:5
HIGHHOPES
UP
LOWFEELINGS
UP
UPANDDOWN
DOWN
IAMSTILLSTANDING
DOWN
FOOLINGAROUND
DOWN
样例#1输出:UPANDDOWN
IAMSTILLSTANDING
FOOLINGAROUND
HIGHHOPES
LOWFEELINGS
解题:
制表如下图所示:
可见,对于“UP”的歌曲,上周可能的排名为:(排名+1)~N
同样,对于“DOWN”,上周可能的排名为: (1~排名-1)
而对于“SAME”,我们只需要记录,输出答案时将其照搬原位即可...
可见,越靠前的“UP”可能的排名区间,大于且包含靠后的“UP”的区间
靠后的“DOWN”可能的排名区间,大于且包含靠前的“DOWN”的区间
此后,我们将“UP”、“DOWN”分别用两个不同的vector容器储存,
UP可能的排名从N开始,因此应该从后往前排,
DOWN可能的排名从1开始,因此应该从前往后排,
模拟过程:
“DOWN”中:
“UPANDDOWN”可排区间最小,1~2,置入答案顶部,即1名
“IAMSTILLSTANDING” 、“FOOLINGAROUND”可排区间递增,分别置入2、3名
DOWN区间排序完毕,开始排UP区间
“UP”中:
“HIGHHOPES”、“LOWFEELINGS”可排区间递减,分别置入4、5名
模拟完成,得到正确的样例输出
❀❀❀❀❀❀❀完结撒花❀❀❀❀❀❀❀
AC代码奉上:
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;class Song //歌曲类
{
public:string name;int type; //up:1 same:0 down:-1int index; //区间值,为id+type,用于排序int id; //编号Song() {} //默认构造Song(int id, string name, string change){this->id = id;this->name = name;if (change == "UP")this->type = 1;else if (change == "SAME")this->type = 0;else this->type = -1;this->index = id + type;}
};class MyCompare
{
public:bool operator ()(Song s1, Song s2){return s1.index > s2.index;}
};vector<Song>v, vUp, vDown, vAns;
int n, sameBook[520] = { 0 };int main()
{cin >> n;v.push_back(Song()); vAns.push_back(Song()); //占据0位置,使id对应1~nfor (int i = 1; i <= n; i++){string s, change;cin >> s >> change;Song song = Song(i, s, change);v.push_back(song);switch (song.type){case 1:vUp.push_back(song);break;case -1:vDown.push_back(song);break;case 0:sameBook[i] = 1; //记录此samebreak;}}sort(vUp.begin(), vUp.end(),MyCompare()); //按index排序sort(vDown.begin(), vDown.end(), MyCompare());for (int i = 1; i <= n; i++){if (sameBook[i]){vAns.push_back(v[i]); //same直接置入答案,跳过continue;}if(vDown.size()){vAns.push_back(vDown.back());vDown.pop_back();continue;}vAns.push_back(vUp.back());vUp.pop_back();}for (int i = 1; i <= n; i++)cout << vAns[i].name << endl;return 0;
}
更多推荐
洛谷P1159 排行榜
发布评论