官方题解

题目大意

有一个仅包含 . 和 X 的字符串，最多替换 $k$ 的 . 为 X ，问最多能使多少个 X 连续。

解题思路

本体可以使用双指针或二分答案。

考虑双指针，优先滑动右端点 $r$ ，记录区间内 . 的数量，当数量大于 $k$ 时，移动左端点 $l$ 直至区间内 . 的数量小于等于 $k$ 。时间复杂度为 $O(n)$ 。

考虑二分，我们可以用前缀和维护 X 的数量，二分求区间长度，遍历是否可以构成长度为 $mid$ 的字串即可。时间复杂度为 $O(n\log n)$

参考答案

方法一：双指针

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int k;
	cin>>s>>k;
	s=' '+s;
    int cnt=0,ans=0;
	for(int i=1,j=0;i<s.size();i++){
		while(cnt<=k && j<s.size()){
            if(s[++j]=='.') cnt++;
        }
		ans=max(ans,j-i);

		if(s[i]=='.') cnt--;
	}
	cout<<ans;
	return 0;
}

方法二：二分

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;

string t;
int k;
int s[N];

bool check(int x){
	for(int i=x-1;i<t.size();i++)
		if(s[i+1]-s[i-x+1]<=k) return true;
	return false;
}

int main(){
	cin>>t>>k;
	for(int i=0;i<t.size();i++){
		if(t[i]=='.') s[i+1]++;
		s[i+1]+=s[i];
	}

	int l=1,r=t.size();
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
    cout<<l-1<<endl;
	return 0;
}