Visits: 272

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;
}