本文共 1113 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到一个最大的区间，使得该区间内的牛的种族平衡，即种族0和种族1的数量相等。我们可以通过将问题转化为求最长子数组和为零的区间来解决。

方法思路

解决代码

n = int(input())cows = []for _ in range(n):    s, x = map(int, input().split())    cows.append((x, s))cows.sort()values = [1 if s == 1 else -1 for x, s in cows]x_list = [x for x, s in cows]prefix = [0] * (n + 1)for i in range(1, n + 1):    prefix[i] = prefix[i-1] + values[i-1]pos = {}for i in range(n + 1):    current = prefix[i]    if current not in pos:        pos[current] = [i, i]    else:        pos[current][1] = imax_diff = 0for key in pos:    first, last = pos[key]    current_diff = x_list[last - 1] - x_list[first - 1]    if current_diff > max_diff:        max_diff = current_diffprint(max_diff)

代码解释

这种方法的时间复杂度为O(n log n)，主要来自于排序步骤，适用于较大的输入规模。

转载地址：http://sfezz.baihongyu.com/