容易发现当 k 增加时，覆盖的 1 的数量的增量是单调不增的，因此覆盖的 1 的数量关于 k 是一个上凸函数，可以使用 wqs 二分。

贴两个链接，感兴趣的可以学一学。

wqs 二分学习笔记

一种基于 wqs 二分的优秀做法

###C++

class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.size();
        vector<int> pre(n);
        pre[0] = (floor[0] == '1');
        for (int i = 1; i < n; ++i) {
            pre[i] = pre[i - 1] + (floor[i] == '1');
            if (i >= carpetLen) {
                pre[i] -= (floor[i - carpetLen] == '1');
            }
        }

        vector<int> f(n), g(n);
        int l = 0, r = n, ans = 0;
        while (l <= r) {
            f[0] = g[0] = 0;
            int mid = (l + r) / 2;
            for (int i = 0; i < n; ++i) {
                if (i != 0) {
                    f[i] = f[i - 1];
                    g[i] = g[i - 1];
                }
                if (i >= carpetLen) {
                    int use = f[i - carpetLen] + pre[i] - mid;
                    if (use > f[i]) {
                        f[i] = use;
                        g[i] = g[i - carpetLen] + 1;
                    }
                }
                else {
                    int use = pre[i] - mid;
                    if (use > f[i]) {
                        f[i] = use;
                        g[i] = 1;
                    }
                }
            }
            
            if (g[n - 1] <= numCarpets) {
                ans = f[n - 1] + mid * numCarpets;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }

        int cnt1 = 0;
        for (char ch: floor) {
            cnt1 += (ch == '1');
        }
        return cnt1 - ans;
    }
};