洛谷P2988 - Test Taking

作为一道英文题，我们先解释一下题意：

给你一个长度为 $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 的情况。

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

以下为代码：

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