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;
}