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

发布于 2022-10-26  287 次阅读


题目链接:最长的 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;
}