洛谷P2988 - Test Taking

 OI / 洛谷
被浏览

作为一道英文题,我们先解释一下题意:

给你一个长度为 $n$ 的 01 串,其中可能至少有 $t_{i}$ 个 1,问最后你给出一个 01 串可能和其匹配的最大长度。

接下来我们进入正题。

第一眼看见觉得是水题,对于每个 $t_{i}$ 枚举应该全 0 还是全 1,但是这显然可以找出反例来。

那么我们应该怎么贪心呢?

首先,我们先提出一个引理:

对于两个长度为 $n$ 的 01 串,$A$ 中 $a$ 个 1,$B$ 中 $b$ 个 1,任一排列中相同位置元素相同的数量至少为 $\max\{a+b-n,n-a-b\}$。

接下来我们证明一下。

1、$a+b>n$,即 $A$ 和 $B$ 匹配 1。

我们为了让相同元素尽可能少,考虑把 $A$ 中的 1 全移到前端,$B$ 中的 1 全移到后端,变成线段覆盖问题,重合部分为 $a+b-n$。

2、$a+b<n$,即 $A$ 和 $B$ 匹配 0.

同理,我们考虑把 $A$ 中的 0 全移到前端,$B$ 中的 0 全移到后端,用同样的方法得出该情况下结果为 $n-a-b$。

3、$a+b=n$,显然答案为 0。

说完了引理,我们再接着讲题。

我们先将 $t$ 从小到大排序,设当前要匹配的 01 串为 $S$,其中有 $x$ 个 1。

对于每对 $t_{i-1},t_{i}$,我们肯定是拿 $S$ 和 $t_{i-1}$ 去匹配 0,和 $t_{i}$ 去匹配 1。

由引理得 $Ans=\max\{n-t_{i-1}-x,t_{i}+x-n\}$。

当 $n-t_{i-1}-x \geq t_{i}+x-n$ 时,

得 $Ans \geq (t_{i}-t_{i-1})/2$

同理当 $n-t_{i-1}-x \geq t_{i}+x-n$ 时,

得 $Ans \geq (t_{i}-t_{i-1})/2$

综上所述,必有 $Ans \geq (t_{i}-t_{i-1})/2$。

然后特判一下 $t_{1}$ 和 $t_{m}$,全选 0 或全选 1 的情况。

于是我们就可以愉快地切题了。

以下为代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define gc c=getchar()
int read() {
int x = 0, f = 1; char gc;
for (; !isdigit(c); gc)if (c == '-')f = -1;
for (; isdigit(c); gc)x = x * 10 + c - '0';
return x * f;
}
#undef gc
int a[10005];
int main() {
int n = read(), m = read();
for (int i = 1; i <= m; i++)a[i] = read();
sort(a + 1, a + m + 1);
int ans = max(a[1], n - a[m]);
for (int i = 1; i <= m; i++)ans = max(ans, (a[i + 1] - a[i]) / 2);
printf("%d", ans);
}