题解：P11561 【MX-X7-T2】[LSOT-3] 姬誉蛙

jinhangdong · 2025-01-11 19:08:44 · 题解

二分答案，每次看看至少需要分成几块 \le k 就移右端点，否则移左端点。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r=1e18,n,k;
string s;
bool check(int x)
{
    int cnt=1,c1=0,c0=0;
    for(int i=1;i<=n;++i)
    {
        if(s[i]=='1') c1++;
        else c0++;
        if(c1*c0>x)//说明需要新的块
        {
            cnt++;
            c1=0,c0=0;
            if(s[i]=='1') c1++;
            else c0++;
        }
    }
    return cnt<=k;
}
signed main()
{
    cin>>n>>k;
    cin>>s;
    s=" "+s;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r;
    return 0;
}