【数学-贪心-末状态已知】问题集合

关于本题的“想一想为什么”：因为非齐次方程组的系数行列式为0，所以方程的解不唯一，所以最后一个方程没有贡献。

末态相同的题目，可以往方程组方向去想。最后可以往坐标的距离方面去靠。

本题第一个设想“有一个雕塑不会动”的证明：

设开始每个墓碑相差A，移动后每个墓碑相差M，M可以不相同，因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

[latex][/latex] $A-X_1+X_2=M =>X_2=X_1-(A-M)$

$A-X_2+X_3=M =>X_3=X_1-2(A-M)$

$\dots$

$A-X_n+X_1=M =>X_n=X_1-n(A-M)$

同样可以变成X1到各个数字的距离最小的问题，即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案，因为M仅仅是假设存在一个M使其满足末态，由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解

发表评论 取消回复