本文共 1154 字，大约阅读时间需要 3 分钟。

开始一直不知道怎么写

但是可以枚举$A$串的右端点和$B$串的左端点

然后可以一直把$A$串向左扩展,$B$串向右扩展

而且因为$dis$是个单增函数,所以一旦大于$m$就可以直接跳出

但这样没有优化复杂度,仍然是$O(n^3)$

究其原因,是因为枚举端点就花了$O(n^2)$

但是对于A串和B串,如果A串向右延伸,B向左延伸

最后会交于他们的对称轴,我们可以枚举这根对称轴

设对称轴左边是$mid$,对称轴右边是$mid+1$

那么当前A串区间是$[mid,mid]$,B串区间是$[mid+1,mid+1]$

如果要维持对称轴不变,要么A左端点左移一个长度,B右端点右移一个长度

要么A右端点左移一个长度,B左端点右移一个长度

$那么这样就是一个尺取的过程,因为dis是一个不减函数$

#include 
   
    using namespace std;const int maxn = 5009;char s[maxn];int T,n,m;void solve(int i,int x,int &ans){
   	int l1 = i, r1 = i,l2 = i+x,r2 = i+x;//中心轴的右边	int sumn = abs( s[l1]-s[l2] );	while( l1>=1&&r2<=n )	{
   		if( sumn<=m )		{
   			ans = max( ans,r1-l1+1 ),l1--,r2++;			sumn += abs( s[l1]-s[r2] );		}		else//太大了,缩小 		{
   			sumn -= abs( s[r1]-s[l2] );			r1--,l2++;		}	} 	}int main(){
   	cin >> T;	while( T-- )	{
   		cin >> m >> (s+1);		n = strlen( s+1 );		int ans = 0;		for(int i=1;i<=n;i++)//中心轴的左边 			solve(i,1,ans),solve(i,2,ans);		printf("%d\n",ans);	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109735653 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！