Because of the greedy
by Chloris @ 2018-04-24 22:48:06
首先我们确定一个问题,纸牌只能向相邻的堆移动 。
其实这就很像一个第一次上体育课的问题。
假设老师让一群人站成一排,但是呢大家初来乍到都不熟悉只能和自己刚认识的朋友站在一起。
那么就产生了一个问题,老师面对着一群学生,他们的身高是这样:
1、2、3、3、4、1、3、2 ...
参差不齐的感觉。
现在老师要把他们按某种顺序排列,是不是应该从左往右安排一下。
因为如果先安排中间的话,假设安排好了第n个人的身高.n-1位置的人和n+1位置的人没有安排好.
那么假设n-1和n+1位置的人需要互换位置呢?
因为只能相邻移动,所以n+1先和n换位置再和n-1换位置,n-1再和n换位置.才达到了目标.
n本来是被安排好了的,在这次移动中就造成了两次多余的对它来说没必要的移动.
emmm...这道题的算法标签也是贪心吧,对于某个个体只考虑局部最优解.
如果我们从左往右考虑的话,第一个人位置挪好了.就可以看作是"出队"了.就当作它不存在就行了.
如此一来,从左往右依次考虑得到的就是最优解了.
蒟蒻的一发回答...可能把问题说的更复杂了.
各位dalao看到了别喷我.
by 温情 @ 2018-04-25 08:52:16
###### 第一个不能向左移
------------
所以从i到n-1循环中有三种情况：
```
1：a[i]小于平均数 把右边的移过来
2：a[i]等于平均数 不用管
3：a[i]大于平均数 把这边的移到右边
```
每次都把a[i]置为平均数
------------
n-1次后，a[n]也会变成平均数
### 然后就可以了
by 蒟蒻lxy @ 2018-06-22 19:59:31
因为右边的已经移好了，如果再往右移的话，右边就又乱了，所以只能往左边移。
by joker_july @ 2018-06-24 15:51:48
我是这样想的：如果一个牌堆的牌小于平均值的话，那就肯定要借牌，可以向左也可以向右，因为不管向左或者是向右都是要向多的牌堆借，而且借的次数都是一样的，所以就索性只往一个方向（右）借。
by Ank1Ng @ 2018-07-05 16:51:57
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
by BirB @ 2018-07-24 08:13:57