P13235 [GCJ 2015 Finals] Pretty Good Proportion

我有一个长度为 $N$ 的二进制数字序列。我正在寻找一个子串，使得其中 $1$ 的比例恰好等于给定的分数 $F$，但这样的子串可能不存在，所以我会选择一个比例最接近 $F$ 的子串。 你能找到一个子串，使得其中 $1$ 的比例尽可能接近给定的分数 $F$ 吗？请输出这样一个子串最早出现的起始下标。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为 $N$ 和 $F$。$F$ 是一个介于 $0$ 和 $1$ 之间的十进制小数，且小数点后恰好有 $6$ 位。下一行为 $N$ 个数字，每个数字为 $0$ 或 $1$。

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示满足条件的子串的最小起始下标（从 $0$ 开始）。如果有多个答案，输出最小的下标。

**样例解释** 在第 1 组测试数据中，没有子串的 $1$ 比例恰好等于 $666667/1000000$。最接近的比例是 $2/3$。输入字符串中有 $5$ 个子串达到了这个比例——长度为 $3$ 的子串有 $3$ 个，分别从下标 $5, 7, 8$ 开始（$101, 101, 011$）；长度为 $6$ 的子串有 $2$ 个，分别从下标 $5, 6$ 开始（$101011, 010111$）。这些下标中最小的是 $5$。 **数据范围** - $1 \leq T \leq 100$。 - $0 \leq F \leq 1$。 - $F$ 恰好有 $6$ 位小数。 **小数据范围** - 时间限制：5 秒。 - $1 \leq N \leq 1000$。 **大数据范围** - 时间限制：10 秒。 - $1 \leq N \leq 500,\!000$。 由 ChatGPT 4.1 翻译