-
分析
发现每个字符串只会被它的后缀规定，那么就从后往前计算，使得计算每个字符串的时候其后缀已经合法。
因为每一次计算我们都只想删最少的字符，而且删得越少这个字符串的字典序就越大，所以它的前缀的最小字典序就越大，需要删的字符就越少，所以对于每一次计算都只删最少的字符的贪心策略符合全局最优，所以这个贪心策略是正确的。那就删字符使得后面的字符串字典序小于前面，如果发现一个字符大于下一个字符串中这个位置的字符，如果前面已经有一个字符小于这个串了，那么无关紧要，如果没有的话就要删除这一段后缀。
值得注意的是，每次比较的下一个字符串都是已经修改过的下一个字符串，因为如果是原字符串所要求的最小字典序可能会比原来小，使一些本该删除的字符没被删导致答案错误。
因为我们删除字符时是一个个枚举的，那么总的时间复杂度就是 \(\mathcal{O(\sum_{i=1}^{n} len_{i})}\)，可以通过此题。 -
代码
#include <iostream>
using namespace std;
constexpr int MAXN(1000007);
string s[MAXN];
int len[MAXN];
int n;
inline void read(int &temp) { cin >> temp; }
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(n);
for (int i(1); i <= n; ++i) cin >> s[i];
len[n] = (int)s[n].length() - 1;
for (int i(n - 1); i; --i) {
int misaki(0);
len[i] = -1;
for (; misaki < (int)s[i].length(); ++misaki) {
if (s[i][misaki] > s[i + 1][misaki] || misaki > len[i + 1]) {
--misaki, len[i] = misaki;
break;
}
if (s[i][misaki] < s[i + 1][misaki]) break;
}
if (!~len[i]) len[i] = (int)s[i].length() - 1;
}
for (int i(1); i <= n; ++i) {
for (int j(0); j <= len[i]; ++j) cout << s[i][j];
cout << endl;
}
return 0;
}