CF1809D Binary String Sorting

简要题意

给定一个串，要求你交换相邻两个数或删掉一个数，使得该串单调不降。其中交换相邻两个数的代价是，删除的代价是，求最小代价。

策略分析

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

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

时间复杂度。

参考代码

#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();
}