ZR1540 小W与制胡串谜题

zrzring 2020-11-18 PM 9℃ 0条

输出给定n字符串拼凑出的字典序最小的字符串

很多年前的结论题,当时水平不太够所以没有理解很透彻,考试时候想到的是类似于SA的双关键字排序,但是并没有通过此题

排序,对于两个字符串a,b,若$a + b < b + a$,则a在前面,实际上这个式子很直观的表示了题意,所以正确性即为定义

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
void file() {
    freopen("std.in", "r", stdin);
    freopen("wa.out", "w", stdout);
}
const int N = 1e6 + 10, inf = 1e9;
inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
struct NODE {
    int c[11], len;
} str[N], cpy[N];
int n, m, t1[30], t2[30];
char ch[11];
bool cmp(NODE a, NODE b) {
    for (int i = 1; i <= a.len; i++) t1[i] = a.c[i];
    for (int i = 1; i <= b.len; i++) t1[i + a.len] = b.c[i];
    for (int i = 1; i <= b.len; i++) t2[i] = b.c[i];
    for (int i = 1; i <= a.len; i++) t2[i + b.len] = a.c[i];
    for (int i = 1; i <= a.len + b.len; i++) {
        if (t1[i] != t2[i]) return t1[i] < t2[i];
    }
    return 0;
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        scanf("%s", ch + 1); str[i].len = strlen(ch + 1);
        for (int j = 1; j <= str[i].len; j++) str[i].c[j] = ch[j] - 'a';
    }
    sort(str + 1, str + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= str[i].len; j++) putchar(str[i].c[j] + 'a'); 
    }
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00