P14576 Lamborghini (Remix) 题解

1. 题意解释

给出一段

n

行的代码，每行的长度为

a_i

，你可以在某些行的末尾处放上光标，并使所有光标移动任意次，求一行上最多可以有多少个光标。

2. 思路

可以知道这一行的光标编号一定是连续的，且不论怎么移动，光标间的距离是保持不变的。

因此我们可以预处理光标距离的前缀和，以做到

O(1)

查询两个光标间的距离。

然后我们发现答案是有单调性的，考虑二分答案。

考虑对于光标数量

x

如何判断正确性。

枚举第一个光标的编号

i

，则这一串光标的总长度即为

sum_{i+x-1}-sum_i

。

如果代码中有一行的长度大于等于光标总长度，那么我们总可以通过移动把这一串光标移到这一行。

所以我们只需要判断

sum_{i+x-1}-sum_i

是否小于等于最长代码行的长度就可以了。

有一些细节见代码注释。

3. 代码实现

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[200200],sum[200200],ans,maxn;
bool check(int x){
	for(int i=1;i+x-1<=n;i++){
		int l=sum[i+x-1]-sum[i];//注意第 i 个光标的距离是不算在内的，所以这里是 sum[i] 而不是 sum[i-1]
		if(l<=maxn){
			return true;
		}
	}
	return false;
}
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		sum[0]=0;
		maxn=-1e9;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			a[i]++;//光标从当前行移动到下一行还要一次移动，所以相当于代码行长度加一
			sum[i]=sum[i-1]+a[i];
			maxn=max(maxn,a[i]-1);
		}
		int l=1,r=n;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(mid)){
				ans=mid;
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

P14576 Lamborghini (Remix) 题解

文章操作

1. 题意解释

2. 思路

3. 代码实现

相关推荐

评论

P14576 Lamborghini (Remix) 题解