Educational Codeforces Round 96 D. String Deletion -- 尺取

题目描述:

题目大意:

给出一个由 0 和 1 组成的字符串,可以对字符串进行操作,每次操作分为两步:

1. 删掉某个位置上的字符。

2. 将前缀字符相同且数量最大的所有字符删掉。

问最多可以将这个字符串最多操作多少次？

侃侃:

题目要求我们求出这个字符串可以最多操作多少次,那么我们就需要采取一种策略使得每次选择的结果是最优的。
如果字符串中相邻的字符之间都是不同的,例如 101010,我们从某个位置删掉一个字符后,由于前缀中没有相同的,所以删掉第一个就可以。
如果字符串中相邻的字符之间有相同的,则存在比较优秀的选择，例如 111011,如果我们选择删除 0 ,第二步的时候就需要删除前缀 111,剩下 11,但是如果第一次删除的是 第 2 个位置上 的 1,那么前缀就是 11,剩下的就是 011,这样就可以增加我们的操作次数了。
如果前缀中没有相同的字符,而是在中间或者其他位置有相同的字符: 101110,如果删除掉第二个字符,剩下 11110,再删除前缀就只剩下 0, 但是如果我们删除 中间 三个 1 的一个,此时字符串时 10110,再删除前缀 0110,之后再从中间数量较多的进行删除一个,再删前缀,这样无疑可以增加我们的操作次数。

通过上述的分析,我们可以了解到, 相同字符的数量是我们所必须要知道的,我们可以用一个数组 cnt 用来存储每个位置相同字符的数量,之后尺取这个数组即可。

Code

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 10;

int cnt[maxn],a[maxn];

char c[maxn];

int t,n;

int main(void) {
	scanf("%d",&t);
	while(t --) {
		scanf("%d",&n);
		string str;
		cin >> str;
		// 将字符串转换为数字 
		for(int i = 0; i < str.length(); i ++) {
			a[i + 1] = str[i] - '0';
		}
		int l = 1, r = 1,num = 1,ans = 0;
		// 最后那个要加上
		a[n + 1] = -1;
		// 统计每段相同字符的个数放到 cnt[] 数组中 
		for(int i = 2; i <= n + 1; i ++) {
			if(a[i] == a[i - 1]) {
				num ++;
			} else {
				cnt[++ ans] = num;
				num = 1;
			}
		}
		if(ans == 1) {
			printf("1\n");
			continue;
		}
		int res = 0;
		// 尺取的是得到的 cnt[] 数组
		while(l <= r && l <= ans) {
			// 如果当前前缀相同字符 >= 2 ,采取最优的策略 
			if(cnt[l] >= 2) {
				res ++;
				l ++;
			} else {
				while(r <= ans) {
					// 查询中间或者末尾是否有 相同字符数量 >= 2的 
					if(cnt[r] == 1) r ++;
					else break;
				}
				if(cnt[r] >= 1 && r <= ans) {
					cnt[r] --;
					l ++;
				} else {
					// 后面都没有相同的字符数量了,那就只能从头删除(每次操作有两步) 
					l ++;
					l ++;
				}
				res ++;
			}
			// 保持 r 和 l 的同步(主要是 前缀时,l 移动了, r 没有动) 
			while(r < l) r ++;
		}
		printf("%d\n",res);
	}
	return 0;
}