最长的Y题解

lewisak / 2024-11-21 / 原文

考虑将 Y 单独拎出来，用数组存储他的下标，那么将第 $x$ 个 Y 转移至第 $y$ 个 Y 就需要
$a[x]-b[y]-1$ 次操作。

发现一个问题：

第一次从左移动至 $y$ 需要减1，第二次从左移动需要减2……

如图：

这似乎是一个很麻烦的问题，我们的某知名 $lyh$ 教授是通过指针（应该是吧）解决的。

但我有一个想法：

假若被转移点和参照点的路径中有别的 Y ,那么因为为了保证最优性，在被转移点左边的点必须先被转移！

听起来有点绕，上图！

那么就可以直接用被转移点前面的 Y 的个数减参照点前面 Y 的个数即可算出应该减多少了：

此部分代码处理：

for(int i=0;i<t.size();i++){
	if(t[i]=='Y'){
		a[++n]=i-n;
		sum[n]=sum[n-1]+a[n];
	}
}

接下来不难发现，经过我们巧妙的处理之后，我们将问题转换成了：

给定一个单调不降的序列，可以对其中的数+1或-1（对应着向左或向右交换）求 $k$ 次操作后最多有几个数一样。

接下来又很容易想到：为了保证最优，一样的数一定是连续的，双（又+又）很容易想到，让连续的一段数一样的最优参照点一定是中位数。

令 $i$ 为区间起点，$x$ 为长度，$sum$ 为前缀和，则转移需要的步数=

\[a[i+x/2]*(x/2)-(sum[i+x/2]-sum[i-1])+\\(sum[i+x-1]-sum[i+x/2-1])-a[i+x/2]*((x-1)/2) \]

这部分的代码处理：

for(int i=1;i<=n-x+1;i++){
	if((a[i+x/2]*(x/2)-(sum[i+x/2]-sum[i-1])+(sum[i+x-1]-sum[i+x/2-1])-a[i+x/2]*((x-1)/2))<=k){
		return 1;
	}
}

然后叒很容易想到，二分长度，枚举起点即可。

最后叕可以发现，时间复杂度 $O(n\log n)$。

ACcode

#include<bits/stdc++.h>
using namespace std;
string t;
int k,a[200100],n,sum[200100];
bool check(int x){
	for(int i=1;i<=n-x+1;i++){
		if((a[i+x/2]*(x/2)-(sum[i+x/2]-sum[i-1])+(sum[i+x-1]-sum[i+x/2-1])-a[i+x/2]*((x-1)/2))<=k){
			return 1;
		}
	}
	return 0;
}
signed main(){
	cin>>t>>k;
	for(int i=0;i<t.size();i++){
		if(t[i]=='Y'){
			a[++n]=i-n;
			sum[n]=sum[n-1]+a[n];
		}
	}
	int l=0,r=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	cout<<r<<endl;
}