#Greedy Algorithm
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
'''
题目：
n堆棋子，每一堆棋子数目不等，但总数为n的整数倍，
每一堆都可向相邻的堆转移不多于本身数目的任意个棋子；
求最少的转移步数使所有的棋子平均分布于各堆
思路：
从第一堆开始，向下一堆转移棋子来是本身棋子数目达到平均数：
若转移数字为正，则记录增加该步骤；
转移数字为0，则为增加步数
当转移数字为负值，步骤也增加一，单顺序应置于下一堆移动之后；
栗子L:
平均值为10
三堆棋子【2，3，25】
第一次 2，3----10，-5 （-8，负值所以应为第二部）
第二次 -5 ，25 -----10，10 （-15，实际第一步）
实际操作步骤为：
3，25----18，10
2-18----10，10

'''
import numbers
import numpy as np
import math

#给定数组，相邻元素可以在和不变的条件下，调整大小以求得平均。求最小的调整次数
def digtaltransfer(source=[]):
    sumv=sum(source)
    lengthv=len(source)
    if sumv%lengthv>0:
        print('数组总和应为数组长度的整数倍！')
        return
    differ=0
    steps=[]
    pos=0
    meanv=sumv/lengthv
    for i in range(lengthv):
        differ=source[i]+differ-meanv
        if differ>0 :
            steps.append([i,i+1,differ])
            pos=i
        elif differ<0 :
            steps.insert(pos,[i+1,i,differ])
    print(steps)

a=[1,13,15,27,14,15,13]
digtaltransfer(a)
#给定数组，求得数组最长的摇摆序列（不调整顺序，可删除元素）：
def swinglist(a=[]):
    result=[]
    result.append(a[0])
    result.append(a[1])
    for i in range(2,len(a)):
        if (a[i-1]-a[i-2])*(a[i]-a[i-1])>0 :
            result.pop()
            result.append(a[i])
        else:
            result.append(a[i])
    print(result)
swinglist([1,2,9,3,7,10,11,6,15,9,7,21,24])