训练指南某一题的比例缩放

123

原来是n等分,插入m个元素,仍然要等分,问原来的桩最少移动多少距离

假设总体都是1,原来在1/3,后面插入一个点,变成四等分,那么总体还是1的话

那么位置仍然在1/3,但如果我们要变成,每一个等分的距离是1,比如说4等分变成0,1,2,3

那么我们原来在1/4的点会变成1,所以同理,1/3就会变成1/3*(3+1),4/3

所以说按照这个比例变换,曾经在等分点上的位置现在都应该在,i/n*(n+m)

所以这个公式是这么来的,那么对于左右两个等分的整点,我们选择哪一边呢,那么四舍五入就好,哪边近选哪边

会不会有两个原来的点选统一个后面等分的整点呢?(由于原先的等分性,不会的,但我好像不太会证...

该算法还有一个前提就是,假设有一个点是不动的,所以我们把该点作为参考点,相当于建立了一个圆上的坐标系

原文地址:https://www.cnblogs.com/linkzijun/p/6940294.html