移除所有载有违禁货物车厢所需的最少时间

题目

2167. 移除所有载有违禁货物车厢所需的最少时间

---

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

1. 从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
2. 从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
3. 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。

返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

示例 1：

输入：s = "1100101"
输出：5
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 1 次。所用时间是 1 。
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2 + 1 + 2 = 5 。

一种替代方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间也是 2 + 3 = 5 。

5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

示例 2：

输入：s = "0010"
输出：2
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间是 3.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
总时间是 2.

2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

提示：

• 1 <= s.length <= 2 * 10^5
• s[i] 为 '0' 或 '1'

题解

方法一：

思路

p[i] 为前i个数的前缀和，p[0] = 0

设0<=l<=r<=n

我们让s[0...l-1]的数执行操作1，用时l

我们让s[r...n-1]的数执行操作2，用时n-r

我们让s[l...r-1]的数执行操作3，用时2*(p[r]-p[l])

总用时2*(p[r]-p[l])+l+n-r = 2*p[r]-r-(2*p[l]-l)+n
令A[x] = 2*p[x]-x

则总用时A[r]-A[l]+n

问题转化为找A[r]前最大的数A[l],使得总用时最小

代码

class Solution {
public:
    /*
        p[i] 为前i个数的前缀和，p[0] = 0
        s[l...r-1]的数是操作3，用时2*(p[r]-p[l])
        s[0...l-1]的数是操作1，用时l
        s[r...n-1]的数是操作2，用时n-r
        总用时2*(p[r]-p[l])+l+n-r = 2*p[r]-r-(2*p[l]-l)+n
        令A[x] = 2*p[x]-x
        则总用时A[r]-A[l]+n, 0<=l<=r<=n
        问题转化找A[r]前最大的数A[l],使得总用时最小
    */
    int minimumTime(string s) {
        int n = s.size();
        vector<int> p(n+1, 0);
        for (int i=1; i<=n; i++) {
            p[i] = p[i-1] + s[i-1]-'0';
        }
        for (int i=0; i<=n; i++) {
            p[i] = p[i]*2-i;
        }
        int ans = n, mx=p[0];
        for (int i=0; i<=n; i++) {
            mx = max(mx, p[i]);
            ans = min(ans, p[i]-mx+n);
        }
        return ans;
    }
};

方法二：

思路

令pre[i]为0…i先用操作1再用操作3的最小单位时间数。

令puf[i]为i..n-1先用操作3再用操作2的最小单位时间数。

这样答案就是max(pre[i]+suf[i+1])

考虑pre[i]状态转移

如果s[i] = '1'，可以考虑用什么操作删除s[i]，若操作3删除则可由pre[i-1] + 2转移；若用操作1删除则由i+1转移。即pre[i] = min(pre[i-1]+2, i+1)。

如果s[i] = '0'，pre[i] = pre[i-1]。

suf[i]状态转同理

当s[i] = '1'，suf[i] = min(suf[i+1]+2, n-i)

当s[i] = '0'，suf[i] = suf[i+1]

代码

class Solution {
public:
    int minimumTime(string s) {
        int n = s.size();
        if (n == 1) return s[0]=='1';
        vector<int> pre(n, s[0]=='1'), suf(n, s[n-1]=='1');
        for (int i=1; i<n; i++) {
            if (s[i] == '1') pre[i] = min(pre[i-1]+2, i+1);
            else pre[i] = pre[i-1];
        }
        for (int i=n-2; i>=0; i--) {
            if (s[i] == '1') suf[i] = min(suf[i+1]+2, n-i);
            else suf[i] = suf[i+1];
        }
        int ans = n;
        for (int i=1; i<n; i++) {
            ans = min(ans, pre[i-1]+suf[i]);
        }
        return ans;
    }
};