[代码源OJ]#999. 最长的 X（二分 or 双指针）

题目链接：最长的 X - Problem - Daimayuan Online Judge

ETOJ：P1003 - 最长的1 - ETOJ (eriktse.com)

有两种做法，第一种是二分。

解法一：二分

先将给定的序列转换成01串，其中'.'换成0，'X'换成1。

再给01串求一个前缀和记录0的个数，现在开始枚举右端点，然后二分得到左端点。

不难发现左端点应该尽可能原理右端点且区间[l, r]中0的个数应该小于等于K。

对于一个右端点R，如何找到左端点L呢？

注意前面前缀和记录的是0的个数，所以我们通过prefix[r] - prefix[l - 1] <= K变形得到prefix[l - 1] >= prefix[r] - K，又因为l要尽可能远离r，也就是尽可能小，所以我们求到的第一个大于等于prefix[r] - K的点就是l - 1，再将这个点+1得到的就是l。

最后和ans取大即可，时间复杂度O(NlogN)。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;

char s[maxn];
int a[maxn], prefix[maxn];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> s + 1;
	int K;cin >> K;
	int N = strlen(s + 1);
	for(int i = 1;s[i]; ++ i)a[i] = s[i] == '.' ? 0 : 1;
	
	for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] + (a[i] == 0);
	int ans = 0;
	for(int r = 1; r <= N; ++ r)
	{
		//l - 1的取值范围是[0, r - 1]
		int l = lower_bound(prefix, prefix + r, prefix[r] - K) - prefix + 1;
		ans = max(ans, r - l + 1);
	}
	cout << ans << '\n';
	return 0;
}

解法二：双指针

如果你在解法一中将l, r全部打印出来不难发现l, r都是单调不减的。

现在假设一个区间[l, r]，我们可以很快的得到其中1的个数，0的个数。

那么如果区间中0的个数<=K，说明区间可以变大，如果向右移动l只会使得0的个数更少，所以r可以变大（为什么不是l变小呢？因为我们确定的正方向是向右的，如果要l变小，需要反向地进行）。

如果发现区间中0的个数>K说明区间太大了，如果向右移动r只会使得0的个数更多，更加不满足条件，所以需要右移l。

可以预处理前缀和，也可以用俩变量来记录。注意初始条件rsum = a[1]。

时间复杂度O(N)。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;

char s[maxn];
int a[maxn];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> s + 1;
	int K;cin >> K;
	int N = strlen(s + 1);
	for(int i = 1;s[i]; ++ i)a[i] = s[i] == '.' ? 0 : 1;
	
	int ans = 0, lsum = 0, rsum = a[1];
	//时刻保持i <= j 
	for(int i = 1, j = 1;j <= N; rsum += a[++ j])
	{
		while(rsum - lsum < j - i + 1 - K)lsum += a[i ++];
		//经过while后（1的个数）rsum - lsum >= j - r + 1 - K
		//变换一下也就是0的个数 <= K了 
		ans = max(ans, j - i + 1);
	}
	cout << ans << '\n';
	return 0;
}