120561D

https://ac.nowcoder.com/acm/contest/120561/D

赛时想到了二分，但是没想好的检验策略。赛后看好像上ST表也能做，但是太麻烦了就不写了。

后面补题的时候尝试自己再想想，发现思维难度还是有的。主要是想复杂了，当时想的是维护跳一步能到的最远距离，以及在自己到最远距离之间一步跳的最远的点。事实上写下来就是很复杂，一堆细节，还容易TLE。后面看了正解做法，只需要维护：在自己左边及自己的所有点中，能跳的最远的距离是多少。因为每个点都要染色，所以一定从左往右，这样做一定不劣。这样就很好实现了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10001000],bg,ne[1000100];
int read(){
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int pd(int lim){
	int res=1,t=0;
	for(int i=bg;i<=n;){
		t++;
		i=ne[i];
//		cout<<lim<<'r'<<i<<endl;
		if(i>=n) break;
		if(i==ne[i]){
			while(i<=n&&ne[i]==i) i++;
			if(i<=n){
				t=0;
				res++;
			}
		}else{
			if(t==lim){
				i++;
				while(i<=n&&!a[i]) i++;
				if(i<=n){
					res++;
					t=0;
				}
			}
		}
	}
//	cout<<res<<endl;
	return res<=k;
}
void work(){
	for(int i=1;i<=n;i++) a[i]=0,ne[i]=0;
	n=read();k=read();
	int h=0;
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]) h++;
	}
	if(h<=k){
		puts("0");
		return;
	}
	while(!a[n]) n--;
	bg=1;
	while(!a[bg]) bg++;
	for(int i=bg;i<=n;i++){
		ne[i]=max(ne[i-1],a[i]+i);
	}
	int l=1,r=n+10;
	while(l<r){
		int mid=(l+r)>>1;
		if(pd(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	if(l!=n+10)
	printf("%d\n",l);
	else
	puts("-1");
}
int main(){
//	freopen("ce.out","r",stdin);
	int t=read();
	while(t--){
		work();
	}
	return 0;
}