题目链接
题意:
\(n\)个以\(#\)开头的由小写字母组成的字符串,求删除最少字母数使得字符串\(s_i\)的字典序不大于\(s_{i+1}\).
思路:
从前往后不好比较,逆向思维。最后一个字符串字典序肯定尽可能大,即不删除字母,然后倒着模拟一下即可。
code:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <deque> #include <cmath> #include <ctime> #include <map> #include <set> #include <unordered_map> #define fi first #define se second #define pb push_back #define endl "\n" #define debug(x) cout << #x << ":" << x << endl; #define bug cout << "********" << endl; #define all(x) x.begin(), x.end() #define lowbit(x) x & -x #define fin(x) freopen(x, "r", stdin) #define fout(x) freopen(x, "w", stdout) #define ull unsigned long long #define ll long long const double eps = 1e-15; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const double pi = acos(-1.0); const int mod = 1e9 + 7; const int maxn = 5e5 + 10; using namespace std; string s[maxn]; int n; int main(){ ios::sync_with_stdio(false), cin.tie(0); cin >> n; for(int i = 1; i <= n; i ++)cin >> s[i]; for(int i = n - 1; i >= 1; i --){ int len = s[i].size(); for(int j = 0; j < len; j ++){ if(s[i][j] < s[i + 1][j])break; else if(s[i][j] > s[i + 1][j] || j >= s[i].size()){ s[i].erase(j); break; } } } for(int i = 1; i <= n; i ++)cout << s[i] << endl; return 0; }