华为OD机试 - 求幸存数之和（Java & JS & Python & C & C++）

题目描述：

在一个社区里有 n 个人，编号为 1 到 n。每个人都有一个特定的健康状态，其中 health[i] 表示编号为 i 的人的健康状态。

每天，每个人都会选择一个编号在 [1, n] 的人与他/她交流。如果两个人交流的次数超过所有其他人的交流次数之和，那么他们就会被确定为“传染者”。

给你一个整数 n 和一个数组 health 。返回使得至少一个人成为“传染者”的最小交流次数。

示例 1：

输入：n = 4, health = [1,1,1,1]

输出：0

解释：无需任何交流，所有人的健康状态都是 1。

示例 2：

输入：n = 2, health = [1,2]

输出：1

解释：需要 1 次交流，编号为 1 和 2 的人进行交流，健康状态变为 [0,0]，就都成为了“传染者”。

示例 3：

输入：n = 4, health = [1,2,3,4]

输出：2

解释：需要 2 次交流，编号为 1 和 2 的人进行 1 次交流，编号为 3 和 4 的人进行 1 次交流，使得健康状态变为 [0,0,0,0]。

提示：

• 1 <= n <= 10^5
• health.length == n
• 1 <= health[i] <= n

解题思路：

这是一个求最小值的问题，可以通过二分查找来实现。首先，我们需要定义一个函数，该函数接收交流次数作为参数，然后检查是否至少有一个人在交流后成为“传染者”。

解决方案：

Java、Python、C、C++ 的代码实现略有不同，但核心思路相同。以下是使用二分查找实现的 Python 代码：

class Solution:
    def minSessions(self, n: int, health: List[int]) -> int:
        def isPossible(x):
            cnt = [0] * n
            for h in health:
                cnt[h - 1] += 1
            for i in range(n):
                if cnt[i] > x:
                    return False
                if cnt[i] == x:
                    cnt[(i + 1) % n] -= 1
            return True
 
        left, right = 0, n * (n - 1) // 2
        while left <= right:
            mid = (left + right) // 2
            if isPossible(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

注意：

• 该解决方案假设交流是双向的，即编号为 i 和 j 的人交流后，编号为 i 和 j 的健康状态都减 1，并且编号为 i+1 和 j+1 的健康状态也减 1。
• 该解决方案使用二分查找来减少时间复杂度，但仍然可能超时，因为时间复杂度为 O(n log(max\_health))。如果需要通过所有测试用例，可能需要优化算法。