Codeforces Round #401 (Div. 2) D. Cloud of Hashtags 贪心、字符串处理

My Solution

题意：给出n个字符串，要求删除尽可能短的后缀，是这n个字符串的字典序是非递减的。

贪心、字符串处理

可知，可以且需要从倒数第二个字符串开始考虑删除后缀，使s[i] <= s[i+1]，因为只能从后往前处理，

然后删除后缀的时候满足删除尽可能短的后缀即可。

复杂度 O(n*length)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 5e5 + 8;

string s[maxn];

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, i, j, sz;
    char ch;
    cin >> n;
    for(i = 0; i < n; i++){ cin >> ch; cin >> s[i];}
    for(i = n - 2; i >= 0; i--){
        if(s[i] < s[i+1]) continue;
        ch = '#';
        sz = min(s[i+1].size(), s[i].size());
        for(j = 0; j < sz; j++){ if(s[i][j] > s[i+1][j]){
                s[i][j] = '�';
                ch = '�';
                break;
            }
        }
        if(ch == '#' && s[i+1].size() < s[i].size()){
            s[i][sz] = '�';
        }
    }
    for(i = 0; i < n; i++){
        cout << "#";
        sz = s[i].size();
        for(j = 0; j < sz; j++){
            if(s[i][j] == '�') break;
            cout << s[i][j];
        }
        cout << "n";
    }

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx