CF578E Walking! 题解
Visits: 312
题意
- 给定一个长度为 $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;
}