[CodeForces]4.7

题目链接：https://codeforces.com/contest/1610/problem/E

灵神描述

输入 t(≤1e4) 表示 t 组数据。所有数据的 n 之和 ≤2e5。

每组数据输入 n(2≤n≤2e5) 和长为 n 的有序数组 a(1≤a[i]≤1e9)，有重复元素。

你需要从 a 中删除一些元素，对于 a 的任意非空子序列 b，都必须满足：

设 avg 为 b 的平均值（可以是小数），b 中比 avg 小的数的个数必须 >= b 中比 avg 大的数的个数。

例如 [1,4,4,5,6] 的平均值为 4，有 1 个数比 4 小，有 2 个数比 4 大，这是不满足要求的。

而 [4,4,5,6] 是满足要求的。

最少需要删除多少个数？

注：子序列不要求连续。

输入

4

3

1 2 3

5

1 4 4 5 6

6

7 8 197860736 212611869 360417095 837913434

8

6 10 56026534 405137099 550504063 784959015 802926648 967281024

输出

0

1

2

3

Solution

from bisect import bisect_left
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    res = 0
    # 初始元素
    for i in range(n):
        l = 0
        diff = 0
        idx = i
        if i > 0 and arr[i] == arr[i - 1]:
            continue
        while idx < n and arr[idx] == arr[i]:
            l += 1
            idx += 1
        while idx < n:
            idx = bisect_left(arr, arr[idx] + diff)
            if idx < n:
                l += 1
                diff = arr[idx] - arr[i]
        res = max(res, l)
    print(n - res)

1.python的数组拷贝操作很费时间。不要这么做。

2.使用PyPy进行提交会更快。