题解：P14576 Lamborghini (Remix)

前置知识

思路

先把问题转化为选择一些行的末尾放置光标，再通过若干次按方向键，使同一行包含所有的光标，求出光标数量的最大值。

注意到光标之间的距离是不变的。

若光标的放置不在连续的行，那么把这些光标转移到一行后，中间某个没光标的行也必在这行中，所以光标放置行数必连续。

易知应该放到最长的行中。

在每个代码长度后加

1

，就可以把光标的位置转化为光标后字符的位置，方便细节处理。

我们预处理出前缀和以快速算出一个区间的总长。

考虑双指针实现计算行数最大值。

代码

CPP

#include<bits/stdc++.h>
#define f(n) for(int i=1;i<=n;i++)
#define int long long
#define endl "\n" 
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
int T,n,a[200005],s[200005],maxl,ans;
signed main(){
	IOS;cin>>T;
	while(T--){
		cin>>n,maxl=-1,ans=-1;
		f(n)cin>>a[i],a[i]++,s[i]=s[i-1]+a[i],maxl=max(maxl,a[i]);//得到前缀和与长度最大值
		for(int l=1,r=1;r<=n;){//经典的双指针 
			if(s[r]-s[l]<maxl)r++;
			else l++;
			ans=max(ans,r-l);
		}
		cout<<ans<<endl;
	}
	return 0;
}

题解：P14576 Lamborghini (Remix)

文章操作

前置知识

思路

代码

相关推荐

评论

题解：P14576 Lamborghini (Remix)