这道题题意很好理解,就是不好写.
题意:给n个初始摊位的位置,然后移动这些摊位使得两两摊位之间的距离都是k;求最小的移动距离的和;
这道题我也是看了题解才明白的;
因为我们是不是最终都会移动到两两距离相等?
意思就是(我们假设开始点为a[0]n=4):
那么是不是最后都会移动到上面的这种样式;
然后我们是不是可以通过题目给出的每个坐标和上面的相应位置相减;
比如我假设起点是1234(其中k是1),题目给出的初始坐标为0125;
然后我们可以发现这个问题;如果我们假设起点是1,那么是不是题目中给出的位置最终都要变成1234这些位置上;
所以我就可以发现上面差值的绝对值的和是不是就是总的移动距离;因为这只是我假设的起点在1时的一种情况下的答案,但是我们要求这个和最小.其实可以假设起点在其他坐标处,但是最后是不是都会变成这种形式:
所以我们是不是可以二分起点?
对了,思路就来了,但是这个起点区间是多少呢?
这个题有点玄学,为什么因为我把二分区间开到1e12才能过,而且还用到了迭代法;
其实这个题的思路已经明白了,就是枚举这个起点,然后不断记录最小答案;
其实这个题有点像白书上面的最大化最小值一样(二分+贪心);但是这个题还有迭代.cout<<ans<<endl;