CF1809 - Educational Codeforces Round 145 (Rated for Div. 2)

D. Binary String Sorting

题意

给出一个仅包含01串s，仅有两种操作

• 交换相邻元素，每次交换的代价是a。（题目中 $a = 10^12$，也就是 $a$ 远大于 $1$）
• 删除任意位置元素，每次删除的代价是a+1。

要求通过多次上述两种操作，使得给出的01串在操作后变为非降的，且具有最小的代价。

也就是要用最小的操作次数，使得最终01串是非降的，并且在相同的操作次数下，交换尽可能多

思路

复杂且错误的dp

开始想的是一个复杂度过高的dp，设 $f(i,j)$ 表示将 s[1...i] 转换为非降的字串所用的最少的代价，则

$$\begin{cases} f(i,j) = \min\{f(i-1,j-1), f(i-1,j)+a+1\}, &s_i = 1,\\ f(i,j) = f(i-1,j) + \min\{a\cdot j, a+1\}, &s_i = 0. \end{cases}$$

时间复杂度：$O(n\cdot \sum_{i}[s_i=1])$，该方法可以拓展用于两种操作代价为任意给定值的问题。（一般化，但复杂度更高）

$[s_i=1]$ 表示中括号内的命题（第 $i$ 个位置 $s_i$ 是 $1$）成立时为 $1$，否则为 $0$。

题解正解贪心

由于删除的优先级相较交换更高，所以我们可以先考虑将所有的删除操作进行完，考虑剩下的交换次数，可以发现交换次数正好是逆序对个数。

假设逆序对个数大于2，则删除该元素比交换该元素代价更小，所以逆序对个数不可能大于1，也就是在删除完全部元素之后，序列一定是 0...001(0)11..1 的样子，所以问题转换为找到最长的 00...0011...111 的字串，并且在长度相同的前提下，记录是否有最左侧的1右边有相邻的0的情况（对应一次交换操作）。

这个操作可以通过记录第 $i$ 个位置后缀1的个数 suf[i]，并记录前面 1...i 中全部0的个数 zeros[i]，将两个进行相加记录最小值 $\displaystyle\min_{i=1}\{\texttt{zeros[i]}+\texttt{suf[i]}\}$，并记录 $i$ 位置右侧第一个1的右边是否有相邻的0，如果有则 neighber[i]=1，否则为0，在 zeros[i]+suf[i] 最小的前提下，判断 neighber[i] 是否可以为1，如果为1则有一次交换更优，否则没有交换。

时间复杂度：$O(n)$

显/隐代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <vector>
#include <map>
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int, int>
#define vip vi<pii>
#define mkp make_pair
#define pb push_back
using namespace std;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int n = s.size();
        vi suf(n+1), neighber(n+1);
        for (int i = n-1; i >= 0; i--) {
            suf[i] = suf[i+1];
            neighber[i] = neighber[i+1];
            if (s[i] == '1') {
                suf[i]++;
                neighber[i] = ((i < n-1 && s[i] == '1' && s[i+1] == '0') ? 1 : 0);
            }
        }
        int mx = suf[0], nei = neighber[0];
        for (int i = 0, zeros = 0; i < n; i++) {
            if (s[i] == '1') continue;
            zeros++;
            if (suf[i] + zeros > mx) {
                mx = suf[i] + zeros;
                nei = neighber[i];
            } else if (suf[i] + zeros == mx) {
                nei = max(nei, neighber[i]);
            }
        }
        if (nei) mx++;
        cout << (ll)((n - mx) * (1e12+1) + (nei ? 1e12 : 0)) << '\n';
    }
    return 0;
}