题D

10%的数据
显然可以直接爆搜，爆搜每一步让哪一只兔子往哪里走。

复杂度O((2n)k)O((2n)^k)O((2n)k)。

20%的数据
这里保证兔子的位置单调递增，显然最终的答案是把一段连续区间里的兔子全部聚在一起，那么我们可以枚举这段区间的左右端点，枚举把兔子聚集到的位置，判断是否能让这段区间内的所有兔子都到达那里。

用最暴力的方法实现，复杂度O(n3max⁡{ai})O(n^3\max{a_i})O(n3max{ai})。

35%的数据
我们可以证明对于一群兔子，设他们的位置为aia_iai，使它们聚集到同一个点时总路程长度最小的位置，是它们的中位数。

考虑若当前把兔子聚集到位置ppp，若ppp不是中位数，则有∑[aip]\sum[a_ip]∑[aip]。

若∑[ai∑[ai>p]\sum[a_i \sum[a_i>p]∑[ai∑[ai>p]，则若它们聚集在p−1p-1p−1，总路程减少∑[aip]\sum[a_ip]∑[aip]。
若∑[ai∑[ai>p]\sum[a_i \sum[a_i>p]∑[ai∑[ai>p]，则若它们聚集在p+1p+1p+1，总路程减少∑[ai>p]−∑[ai<p]\sum[a_i>p] - \sum[a_i<p]∑[ai>p]−∑[ai<p]。
综上，让这些兔子在中位数聚集总路程最少。

因此我们依然可以枚举聚集兔子的区间计算出兔子位置的中位数，然后计算把区间中的兔子聚集在中位数的代价，判断是否满足条件。

时间复杂度O(n3)O(n^3)O(n3)。

50%的数据
给定区间的左右端点显然可以直接计算区间内兔子位置的中位数，我们可以用一些技巧（例如前缀和）直接计算把区间内的兔子聚集在中位数的代价，因此对于每个区间的判断我们只需要O(1)O(1)O(1)的复杂度。

时间复杂度O(n2)O(n^2)O(n2)。

70%的数据
考虑固定左端点，发现区间聚集到中位数的代价关于区间右端点单调，那么我们可以对于每一个可能的左端点，二分右端点的最大位置并统计答案。

时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)

100%的数据
我们还可以发现合法的区间右端点的最大位置是关于左端点位置单调递增的，因此我们使用双指针即可在O(n)O(n)O(n)的复杂度内统计答案。
std：
https://paste.ubuntu.com/p/MrzZm6Zy8V/

总题解参见：https://ac.nowcoder.com/discuss/233498?type=101&order=3&pos=6&page=0