最近想做一些东方的题（毕竟东方也玩了一段时间了233），而且最近在搞二分，于是乎，我阴差阳错的找到了这道题，于是发现这是一道水题，然后么。。呵呵
在写思路之前，先放一些天子的图片233（毕竟题目名字就是天子酱233）。
可爱又傲娇の天子酱QAQ
咳咳，好了言归正传，我们二分一个答案mid为更改的区间长度，然后我们每次扫一遍01串，发现一个1就把后面mid长度的值全赋为0，这样的话一开始我脑洞大开想用线段树来维护QAQ，之后发现对于n=500,000的点实在是有些吃力（线段树常数大，不解释），而且貌似每次验证完还要复原01串，这样的话常数肯定大的飞起。我们不妨再想一个方法，这个方法很机智，遇到1，直接把枚举位置跳过mid位就行了，因为该位后mid位肯定也被赋为0了，所以我们直接跳过这些无用的枚举，而且还不用复原233。这样的话，时间复杂度是O（nlogn）的（事实上还要比这个小，因为跳过枚举的原因）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int maxn=5e5+5; char ss[maxn]; int n,m; bool check(int mid) { int cnt=0; for(int i=1;i<=n;i++) { if(ss[i]=='1') i+=mid-1,cnt++; } if(cnt<=m) return 1; return 0; } int main() { scanf("%d%d",&n,&m); scanf("%s",ss+1); int l=0,r=6e5,mid; while(r-l>1) { mid=l+r>>1; if(check(mid)) r=mid; else l=mid; } printf("%d ",r); return 0; }