洛谷P1159 排行榜

排行榜"/>

洛谷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;
}