0%

[CF1430D] String Deletion

题目

题目链接

题目大意:$t$ 组数据。给出一个长度为 $n$ 的 01 字符串,每次操作可以删去任意一个字符,然后删掉从左开始连续相同的字符,问最多的操作次数。$1 \le t \le 1000, 1 \le n \le 2 \cdot 10^5$。

思路

考虑贪心,显然每次应该删连续的字母。

设 $a$ 数组为字符串每一段相同字符的长度,$a$ 的大小为 $m$,则最多能操作的次数为 $m$。

每次操作应该找从左往右第一个长度不为 $1$ 的连续的段,然后删掉其中的一个字符。

如果运气很好,删 $m$ 次正好删完了,答案就为 $m$。

如果还没删到 $m$ 次,这个字符串里面就没有连续的字符的时候,设已经删了 $k$ 次,那么答案应该为 $k + \lceil \dfrac{m - k}{2} \rceil$。

看到有人说比 C 简单,我倒是感觉 C 比这个简单多了…

考试的时候写了个 $O(n \log n)$ 的,现在想来好像贪心策略就不太对。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

int a[200010];
int n, t, m, l, pos, ans;
char s[200010];
bool flag;

int main() {
read(t);
while (t--) {
read(n);
flag = false;
scanf("%s", s + 1);
l = 1, m = ans = 0;
for (int i = 2; i <= n; ++i) {
if (s[i] != s[i - 1]) {
a[++m] = (i - 1) - l + 1;
l = i;
}
}
a[++m] = n - l + 1;
pos = 1;
for (int i = 1; i <= m; ++i) {
while (pos <= m && a[pos] == 1) ++pos;
--a[pos];
if (pos > m) {
flag = true;
ans = i - 1 + (m - i + 2) / 2;
break;
}
if (pos <= i) pos = i + 1;
}
printf("%d\n", flag ? ans : m);
}
return 0;
}