Azamon Web Services
看到目前题解都是 \(O(n^2)\) 的复杂度，来一发 \(O(nlogn)\) 的贪心题解。
思路很简单，先求经过至多一次的交换后，最小的字符串 \(S\)。再和 \(T\) 比较，如果小于就输出，否则无解。
问题转化成了两个子问题：
- 求经过至多一次的交换后，最小的字符串 \(S\)。
- 和 \(T\) 作比较。
第二个问题很好解决，自己看代码吧，详细说第一个问题。
bool operator < (string a, string b) {
int n = min(a.size(), b.size());
for (int i = 0; i < n; i++) {
if (a[i] < b[i]) return true;
if (a[i] > b[i]) return false;
}
return (a.size() < b.size());
}
贪心地想：字符串最小肯定是让字典序最小的字母尽量靠前。
现在有了初步的思路：用一个堆来维护 \(S\) 中的每个元素，从前往后扫一遍 \(S\)，如果当前元素等于堆顶，弹出堆顶，否则交换并退出循环。
代码：
using pci = pair<char, int>;
bool operator < (string a, string b) {
int n = min(a.size(), b.size());
for (int i = 0; i < n; i++) {
if (a[i] < b[i]) return true;
if (a[i] > b[i]) return false;
}
return (a.size() < b.size());
}
void Sol() {
string s, t;
cin >> s >> t;
priority_queue<pci, vector<pci>, greater<pci>> p;
for (int i = 0; i < s.size(); i++)
p.push({s[i], i});
for (auto &i : s) {
if (i == p.top().first) p.pop();
else {
swap(i, s[p.top().second]);
break;
}
}
if (s < t) cout << s << '\n';
else puts("---");
}
提交后你会发现错了，为什么？
看下面这组样例：
1
AZAAA AAZAA
上面代码所构造出的“最小 \(S\) ”是 AAZAA，这显然不是正确答案。
交换的 A 是要越后面越好，因为在让字典序最小的字母尽量靠前的前提下，让字典序大的字母越靠后越优。
用 set 实现，详细看代码（也没什么细节）。
最终代码：
#include <bits/stdc++.h>
using namespace std;
int read() {
int x;
scanf("%d", &x);
return x;
}
using pii = pair<int, int>;
bool operator < (string a, string b) {
int n = min(a.size(), b.size());
for (int i = 0; i < n; i++) {
if (a[i] < b[i]) return true;
if (a[i] > b[i]) return false;
}
return (a.size() < b.size());
}
set<pii> p;
void Sol() {
p.clear();
string s, t;
cin >> s >> t;
for (int i = 0; i < s.size(); i++)
p.insert({s[i], i});
for (auto &i : s) {
char mn = (*p.begin()).first;
if (i == mn) p.erase(p.begin());
else {
auto it = --p.lower_bound({mn, int(1e9)});
swap(i, s[(*it).second]);
break;
}
}
if (s < t) cout << s << '\n';
else puts("---");
}
int T;
int main() {
T = read();
while (T--) Sol();
}
由于常数和数据等问题，本题时间并不比 \(O(n^2)\) 快多少。