ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年10月26日 153点热度 0人点赞 0条评论

题目链接:最长的 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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: 01串 C++ 二分 代码源 双指针 思维 算法竞赛
最后更新:2022年10月28日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 解法一:二分
  • 代码 / Code
  • 解法二:双指针
  • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号