algorithm - 如何使用二进制搜索解决以下问题？

Question

我们得到了一个整数数组，我们需要找到最小子段的大小，这样在删除它之后数组中的所有元素都是不同的。如何使用 O(nlogn )？我尝试阅读各种使用二进制搜索的提交，但我无法理解它们。

我的尝试 - 我使用蛮力在 n^2logn 中解决了这个问题，但我想知道如何应用二进制搜索来解决 O(nlogn) 中的这个问题。

问题链接 - https://codeforces.com/contest/1208/problem/B

实现二分查找的解决方案之一的链接 - https://codeforces.com/contest/1208/submission/59494540

Answer 1

在链接的解决方案中，如果可以通过删除大小为 siz 的子数组使所有数字唯一，则函数 check(int siz) 返回 true。它在 O(n) 时间内完成。

因为 check(x) == true 意味着 check(y) == true 对于所有 y >= x，main() 函数可以做二分查找找到siz 的最小值使得check(siz) == true，这就是解决方案问题。

如果 check(mid) == true，则答案不大于 mid。如果 check(mid) == false，则答案大于 mid。

二分搜索需要 O(log n) 次检查 的评估，总共 O(n log n) 次。 p>