(题目求助)将01数组中的所有1移动到0元素位置上的最小代价
今天笔试遇到的一个题,搜了半天没找到原题。大家可以帮忙看看有没有现成的题解或者给一点思路吗
题目描述
给定一个长度为n的01数组,其中1的个数不超过n/2,现在要求将数组中的所有1元素移动到0元素的位置上去,其中每个1元素移动的代价为原位置和新位置的距离,总移动代价为所有1元素的移动代价之和。求最小的总移动代价
示例
比如数组[1,1,1,0,0,0],我们一种最佳移动方案为
- 将index 0上的1移动到index 3上
- 将index 1上的1移动到index 4上(不能移动到原来的index 0,哪怕它现在为0)
- 将index 2上的1移动到index 5上
因此最小的总移动代价为9
#笔试##笔试题目#