Vijos 1500 — 笨笨的单词排序

题目描述

笨笨有一些单词，他想要把这些单词按一定顺序排序。

现在笨笨有N(N<=1000)个单词，他想要你按笨笨的字典序把这些单词顺序或逆序排列好来。

输入笨笨的字典序以及他所要排序的单词和他所要的排序方式（顺序或逆序，顺序用1表示，逆序用0表示）。

请你把排好的单词输出,每个单词长度不超过255个字符,中间没有空格。

题目链接

https://www.vijos.org/p/1500

输入格式

第一行，一个长度为26的字母不重复的字符串，表示笨笨的字典序（26个字母全齐）。

第二行一个数N。

接下来N行，每行一个单词。

最后一行是笨笨所想要的排序方式。

输出格式

输出共N行，表示排好序的单词。输出每行一个单词。

样例输入

abcdefghijklmnopqrstuvwxyz
2
big
small
1

样例输出

big
small

提示

是笨笨的字典序，不是一般的字典序哦。

输入输出中的字母均为小写字母。

注：顺序逆序就是说把它们按一定的顺序排列好，而不是要你把单词反过来。

如（按字典序）：
顺序为：
aa
ba
ca
逆序为
ca
ba
aa

题目分析

自己重新定义string的排序规则，然后用sort函数进行排序即可。
使用数组 num 记录每个字母的优先级，就可以使用 num[x-‘a’] 得到字母 x 的优先级值。变量 flag 用来记录数据的要求是顺序还是逆序。
另外，如果两个字符串分别为 s1,s2 且 s2 = s1 + s3（s1是s2的前缀），在顺序排序的时候，要把 s1 放在 s2 前面。至于为啥这样，并不重要，因为 s1 放在 s2 后面会 WA。

AC代码

#include <bits/stdc++.h>
using namespace std;
string p[1005];
char s[30];
int flag, num[30];
bool cmp(const string &s1, const string &s2)
{
    int i, len = min(s1.length(), s2.length());
    for (i = 0; i < len; i++)
    {
        if (num[s1[i] - 'a'] < num[s2[i] - 'a'])
            return flag;
        if (num[s1[i] - 'a'] > num[s2[i] - 'a'])
            return flag ^ 1;
    }
    if (s1.length() < s2.length())
        return flag;
    else
        return flag ^ 1;
}

int main()
{
    int n, i;
    cin >> s >> n;
    for (i = 0; i < 26; i++)
        num[s[i] - 'a'] = i; //i小的优先级大
    for (i = 0; i < n; i++)
        cin >> p[i];
    cin >> flag;
    sort(p, p + n, cmp);
    for (i = 0; i < n; i++)
        cout << p[i] << endl;
    return 0;
}