请求修改题目描述&建议降绿或蓝

SP16809 EST - Estimation

codingwen @ 2025-01-10 19:44:43

这题就是一个裸的中位数预处理,状态转移非常好想。
我这个蒟蒻都做出来了,怎么可能是紫?

题目描述:

给你一个长度为 n 整数数组 A, 称一个数组 B 是合法的,当且仅当:

  • 记 $f(B)=\sum\limits_{i=1}^{n}{| A_i-B_i|}$,求对于所有满足条件的 $B$ 中 $f(B)$ 的最小值。
给你一个长度为 $n$ 整数数组 $A$, 称一个数组 $B$ 是合法的,当且仅当:   
- $B$ 与 $A$ 同长,即 $len_B=n$。
- $B$ 可以被分为 $k$ 段,每段中 $B$ 的值相等,即当 $i,j$ 同属某一段时,有 $B_i=B_j$。      
记 $f(B)=\sum\limits_{i=1}^{n}{| A_i-B_i|}$,求对于所有满足条件的 $B$ 中 $f(B)$ 的最小值。

by codingwen @ 2025-01-10 19:47:35

@minstdfx @realskc @Little09


by codingwen @ 2025-01-10 19:48:07

个人认为此题为上位绿/下位蓝。


|