题解 | #Sequence Coloring#

D题题解：

题目相关知识点：二分答案+贪心

题目分析：由题可知，最短时间具有单调性,即当再t秒染完所有球，t+1秒不发生任何改变，t-1秒球未全部染红。因此通过二分查找将所有红球染红的最小时间t。提前判定t=0的情况，所以从1~n范围内查找t（t<=n,否则输出-1）. 数组nx它的作用是预计算每个位置能覆盖到的最远位置，告诉我们下一步最远能跳到哪里。

代码演示+代码解析:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
const int N = 500010;
int a[N],nx[N];//数组a记录原始数据，数组nx记录位置i能覆盖到的最远位置
int n,k;
int check(int mid){
	int i=1;
	while(a[i]==0){
		i++;
	}//忽略开头的黑色球
	int cnt=1;//cnt记录手动染色个数，第一个白球必须手动染色
	int tim=0;//tim记录当前已染过的范围最右侧的等待时间，第一个白球等待时间为0
	while(i<=n){
		i=nx[i];//遍历到i能覆盖到的位置
        tim++;
		if(i>=n) break;//若>=n代表以全部染完
		if(i==nx[i]){//当前位置无法延伸新的范围
			while(i<=n&&i==nx[i]){
				i++;//将覆盖范围内且无法延伸范围的球遍历完，例如10，5，3，9（遍历到9停下）
			}
			if(i<=n){
				cnt++;//将当前位置手动染色
				tim=0;	//更新当前位置等待时间为0
			}
		}else{
			if(tim==mid){//若当前位置等待时间为mid,为符合题意，当前位置无法向右延伸，只能手动染色下一个白球
				i++;
				while(i<=n&&a[i]==0){
					i++;
				}//忽略黑色球
				if(i<=n){
					cnt++;//手动染色
					tim=0;//更新时间
				}
			}
		}
		
	}
	return cnt<=k;//若在mid时间内，cnt<=k,则符合题意
}
void solve(){
	int cns=0,mi=-1;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>0) cns++;//cns记录白色球的数量
		nx[i]=max(i+a[i],nx[i-1]);
	}
    if(cns<=k){
        cout<<"0"<<endl;
        return;
    }//若白色球数量小于k,直接染成红色，无需等待
	int l=1,r=n,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){//若mid时间内可以全部染红，则向左查找更小的时间
			r=mid-1;
			mi=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<mi<<endl;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int T=1;cin>>T;
	while(T--){
		solve();
	}
	return 0;
}