【二分答案】CF803 D

客官°小女子只卖身不卖艺 2024-03-23 22:41 145阅读 0赞

**感觉之前的\*1900好简单**

[Problem - D - Codeforces][]

题意：

![47e9ce79fee54c63a55acba3cac6e937.png][]

思路：

注意到宽度具有单调性，考虑二分宽度

然后限制了最大宽度，要使行数 <= k

那么在check里贪心，每行选的尽可能多

考虑双指针，每次选长度为mid的区间，然后如果右端点 r 没有指向换行符，那么 r 指向左边离它最近的换行符

所以需要预处理一个位置左边离它最近的换行符的位置

这样就做完了

Code：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    const int N = 1e6 + 10;
    
    std::string s, s2;
    
    int k, len = 0, ns;
    int pre[N];
    
    std::string substr(int l, int r) {
        return s.substr(l, r - l + 1);
    }
    bool check(int mid) {
        std::vector<std::string> res;
        int l = 1, r = 1;
        while(1) {
            if (l > ns || r > ns) break;
            while(r <= ns && r - l + 1 < mid) r ++;
            if (r == ns + 1) r --;
            if (s[r] != ' ' && s[r] != '-' && r != ns) r = pre[r];
            if (l > r) return false;
            res.push_back(substr(l, r));
            l = r + 1;
            r = l;
        }
        return res.size() <= k;
    }
    void solve() {
        std::cin >> k;
        getline(std::cin, s2);
        getline(std::cin, s);
        ns = s.size();
        s = " " + s;
        s = s + " ";
    
        for (int i = 1; i <= ns; i ++) {
            if (s[i] == '-' || s[i] == ' ') {
                pre[i] = i;
            }else {
                pre[i] = pre[i - 1];
            }
        }
    
        //std::cout << check(7) << "\n";
        int l = 1, r = ns;
        int ans = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
        
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/803/problem/D
[47e9ce79fee54c63a55acba3cac6e937.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/29bd719289ab43a7ba709f5843c59fd9.png