题解 洛谷 CF1809D Binary String Sorting

CF1809D Binary String Sorting

简要题意

给定一个 $01$ 串，要求你交换相邻两个数或删掉一个数，使得该串单调不降。其中交换相邻两个数的代价是 $10^{12}$，删除的代价是 $10^{12} + 1$，求最小代价。

策略分析

本题需要我们发现一个重要的性质，因为我们需要把数列变成形如 00000...11111 的形式，所以必然存在一个分界点，这个分解点的两边的数可能是 $10$ 或 $01$。现在假设我们知道这个分界点在哪里了，那么我们就要把分界点左边的 $1$ 想办法弄到右边，或者直接扔掉。我们发现，除非是 $10$ 情况下的分界点左边的那个 $1$，其余的 $1$ 删掉的代价一定比一次一次交换过来少，因为删除只需要一次，而交换至少需要两次，显然 $2 \times 10^{12} > 10^{12} + 1$，处理分界点右边的 $0$ 同理。那么我们只需要枚举这个分界点在哪里，并判断分界点两边的数是 $10$ 还是 $01$ 即可，如果是 $10$ 还要额外判断一下转更优还是不转更优，顺序枚举一遍即可得解。

具体来讲，我们对于每个位置，预处理出其前面（包括自己在内）有多少个 $1$，后面有多少个 $0$，枚举到每一个位置的时候用预处理出的值乘以代价即可，注意预处理的前后缀数组要多组数据清空。

时间复杂度 $O(Tn)$。

参考代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define LL long long
using namespace std;

namespace SHAWN {
    const LL N = 3e5 + 7, C = 1e12 + 1;
    LL q[N], h[N];
    int T;
    signed work()
    {
        cin >> T;
        while (T--) {
            string s; cin >> s;
            int len = s.length();
            s = ' ' + s;
            LL ans = 1e18;
            for (int i = 1; i <= len; ++i) {
                q[i] = q[i - 1];
                if (s[i] == '1') { ++q[i]; }
            }
            for (int i = len; i >= 1; --i) {
                h[i] = h[i + 1];
                if (s[i] == '0') { ++h[i]; }
            }
            for (int i = 0; i <= len; ++i) {
                if (s[i] == '1' && s[i + 1] == '0') {
                    ans = min(ans, q[i - 1] * C + h[i + 2] * C + C - 1);
                }
                ans = min(ans, q[i] * C + h[i + 1] * C);
            }
            cout << ans << '\n';
            for (int i = 0; i <= len; ++i) { q[i] = h[i] = 0; }
        }
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}