Azamon Web Services

看到目前题解都是 \(O(n^2)\) 的复杂度，来一发 \(O(nlogn)\) 的贪心题解。

思路很简单，先求经过至多一次的交换后，最小的字符串 \(S\)。再和 \(T\) 比较，如果小于就输出，否则无解。

问题转化成了两个子问题：

1. 求经过至多一次的交换后，最小的字符串 \(S\)。
2. 和 \(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)\) 快多少。