CF578E Walking! 题解

CF578E Walking!

题意

• 给定一个长度为 $n$ 的只包含 L,R 的字符串 $s$。
• 构造一个 $n$ 排列 $p$ 满足 $s[p_i] \ne s[p_{i+1}](1 \le i < n)$。
• 最小化 $p$ 中 $p_i > p_{i+1}(1 \le i < n)$ 的数量。
• $n \le 10^5$，数据保证有解。

题解

问题等价于，将 $s$ 划分成尽可能少的 L,R 交替的非连续子序列。

考虑贪心，每添加一个字符，就在前面划分好的子序列中找一个可以接到末尾的接进去，没有可以接的就新开一个子序列。

最后要将若干个子序列拼接在一起，分类讨论一下即可。

代码

const int N = 1e5 + 7;
int n, t[N];
char s[N];
vi e[2], Ans;
vector< pi > g[4], ans;

int main() {
	rds(s, n);
	map< char, int > p;
	p['L'] = 0, p['R'] = 1;
	for (int i = 1; i <= n; i++) {
		int c = p[s[i]];
		if (e[c^1].size()) {
			t[i] = e[c^1].back();
			e[c^1].pop_back();
		}
		e[c].pb(i);
	}
	print(e[0].size() + e[1].size() - 1);
	for (ui i = 0; i < e[0].size(); i++) {
		int x = e[0][i], y = x;
		while (t[y]) y = t[y];
		g[p[s[y]]<<1|p[s[x]]].pb(mp(y, x));
	}
	for (ui i = 0; i < e[1].size(); i++) {
		int x = e[1][i], y = x;
		while (t[y]) y = t[y];
		g[p[s[y]]<<1|p[s[x]]].pb(mp(y, x));
	}
	while (g[1].size() > 1u) {
		pi x = g[1].back();
		g[1].pop_back(); 
		t[x.fi] = g[1].back().se;
		g[1].back().se = x.se;
	}
	while (g[2].size() > 1u) {
		pi x = g[2].back();
		g[2].pop_back(); 
		t[x.fi] = g[2].back().se;
		g[2].back().se = x.se;
	}
	if (g[1].size() && g[2].size()) {
		pi x = g[1][0], y = g[2][0];
		g[1].pop_back(), g[2].pop_back();
		if (x.se > y.se) {
			g[0].pb(mp(x.fi, t[x.se]));
			t[x.se] = y.se;
			g[3].pb(mp(y.fi, x.se));
		} else {
			g[3].pb(mp(y.fi, t[y.se]));
			t[y.se] = x.se;
			g[0].pb(mp(x.fi, y.se));
		}
	}
	if (g[0].size() > g[3].size() || (g[0].size() == g[3].size() && !g[2].size())) {
		if (g[1].size()) ans.pb(g[1][0]);
		for (ui i = 0; i < g[3].size(); i++)
			ans.pb(g[0][i]), ans.pb(g[3][i]);
		if (g[0].size() > g[3].size()) ans.pb(g[0].back());
	} else {
		if (g[2].size()) ans.pb(g[2][0]);
		for (ui i = 0; i < g[0].size(); i++)
			ans.pb(g[3][i]), ans.pb(g[0][i]);
		if (g[3].size() > g[0].size()) ans.pb(g[3].back());
	}
	while (ans.size() > 1u) {
		pi x = ans.back();
		ans.pop_back(); 
		t[x.fi] = ans.back().se;
		ans.back().se = x.se;
	}
	Ans.pb(ans.back().se);
	while (t[Ans.back()]) Ans.pb(t[Ans.back()]);
	while (Ans.size()) print(Ans.back(), " \n"[Ans.size()==1u]), Ans.pop_back();
	return 0;
}