题解：CF2042C Competitive Fishing

Hide_In_The_Shadow · 2024-12-03 16:59:03 · 题解

智慧+注意力题。

将 01 序列划分成若干非空段，每段中的点可获得其段下标 -1 的分数，使 1 所得分数比 0 至少大 k；

场上被卡成伞兵了。其实只需要注意到当前点前划分与否对后续序列造成的影响是固定的，问题就迎刃而解了。

我们记 sum[i] 表示到 i 为止的后缀中 1 的个数减去 0 的个数。如果我们在 i 之前划分，则无论后缀序列怎么划分，此处划分的贡献总是 sum[i]。可以感性理解成为后缀赋了一个新的初值继续在后缀上处理原问题。

然后，我们可以对除了 sum[1] 之外的值排序，从大到小取，直到取的值之和 \geq k 或者 sum 为非正数为止，分别对应着最小可行划分数和无解。段数等于划分数 +1。

时间复杂度 O(n\log(n))。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,k,sum[N];
char s[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>k>>s;
        for(int i=n;i>=1;--i){
            sum[i]=sum[i+1]+(s[i-1]-'0'?1:-1);
        }
        sort(sum+2,sum+n+1);
        int ans=0,now=0;
        for(int i=n;i>=2;--i){
            if(sum[i]<=0)break;
            now+=sum[i];
            ans++;
            if(now>=k)break;
        }
        if(now>=k)cout<<ans+1<<'\n';
        else cout<<"-1\n";
        for(int i=1;i<=n;++i)sum[i]=0;
    }
    return 0;
}