logo
publist
写文章

简介

该用户还未填写简介

擅长的技术栈

可提供的服务

暂无可提供的服务

贪心算法:糖果传递

x【i】实际上是一个前缀和,由前面一个状态加上pos-a【j】得到当前状态,所以问题就变成了一堆常数和一个未知数的差值之和怎么样才能更小,这个时候就要用到中位数,只要取到这堆数的中间数作为x【1】的值,那么其他点到这个数的距离之和就是最小的。可以发现其中x【i】都是未知数,如果把他们全部相加会得到没有x数组的一条等式,也就是n条方程只有n-1条是有效的,因此n-1条方程可以解出n-1个未知数,所以

文章图片
#贪心算法#算法
到底了