codeforces1430D String Deletion Educational Codeforces Round 96 (Rated for Div. 2)

题目链接

https://codeforces.com/problemset/problem/1430/D

题目大意

给你一个只包含0,1的字符串，现在你可以对其进行操作

每次操作有两个步骤，且强制执行

1.选择现在剩余字符串的一位（1-n），将选择位的字符删除，且后面的字符前移

2.如果字符串为空，则跳过本步骤。否则，删除最长的含有相同字符的前缀，且后面的字符前移

问你在字符串为空之前最多可执行多少次操作

输入输出

输入

第一行一个t，代表t组数据

每组数据第一行一个n代表字符串长度

随后一个字符串

输出

一个数，代表最大可执行操作

样例

input:

5

6

111010

1

1

1

2

11

6

101010

output:

3

1

1

1

3

思路

我们可以把连续的0，和连续的1看成一段，

那么每次操作可能会删除一段字符串（如：00011，选择第5个字符）

也可能删除两段字符串（如：011，选择第1个字符）

那么经过观测可发现，我们每次选择长度大于一的一段字符串，变可以使本次

操作只删除一段字符串，如果没有就只能删除两段字符串。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2e5 + 5;
vector<int>vec;

char ch[maxn];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		int res = 0;
		vec.clear();
		scanf("%d", &n);
		scanf("%s", ch);
		int nw = 0;
		for (int i = 0; i < n; i++) {
			nw++;
			if (ch[i + 1] != ch[i]) {
				vec.push_back(nw);
				nw = 0;
			}
		}
		int not0ii = 0;
		int cntii = 0;
		int siz = vec.size();
		while (cntii < siz) {
			bool ff = 0;
			while (not0ii < vec.size()) {
				if (vec[not0ii] > 1) {
					vec[not0ii]--;
					ff = 1;
					break;
				}
				else not0ii++;
			}
			if (!ff) {
				if (siz >= cntii) siz--;
				else break;
			}
			vec[cntii] = 0;
			res++;
			cntii++;
		}
		printf("%d\n", res);
	}
	return 0;
}