[CodeForces]4.7
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目链接：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
![[CodeForces]4.7_CF](https://s2.51cto.com/images/202304/f7ba3c5114043a92e4122527fd0bfe8e90ca31.png)
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进行提交会更快。
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |