【园艺师】题解

题意：给定序列h[1]..h[N]，每次可以把相邻的两个元素都减少1，要把序列所有元素变成相同，最少要操作多少次？

【贪心算法】
　　按 h[2]..h[N] 依次考虑每个元素：
　　对于h[2]：
　　　若h[2]<h[1]，则就无解（因为h[1]只能与h[2]一起减少）；
　　　若h[2]>h[1]，需要把h[2]减少成h[1]，把(h[2],h[3])一起减少，操作次数为(h[2]-h[1])，
　　　　　　　　　　此时 h[2]变成h[1]，h[3]变成了 h[3]-(h[2]-h[1])；
　　接着，对于h[3]：
　　　若h[3]<h[2]，则把(h[1],h[2])一起减少成h[3]，操作次数为(h[2]-h[3])；
　　　若h[3]>h[2]，需要把h[3]减少成h[2]，把(h[3],h[4])一起减少，操作次数为(h[3]-h[2])，
　　　　　　此时h[3]变成h[2],h[4]变成了h[4]-(h[3]-h[2])；
　　　……
　　考虑 h[i]：此时意味着h[1]..h[i-1]都变成一样的值，假设为 d。
　　　当h[i]<d时，若i-1是奇数，则无解；否则可把h[1]..h[i-1] 都变成h[i]，操作次数为(d-h[i]) * (i-1) / 2，
　　　　　　　　　此时 d=h[i]；
　　　当h[i]>=d时，需要把h[i]减少成d，方法是(h[i],h[i+1])一起减少，操作次数为(h[i]-d)，
　　　　　　　　　此时d不变，h[i+1]变成了 h[i+1]-(h[i]-d)；
　　　……

　　最后单独处理 h[N]：
　　　若h[N]<d，若N-1为奇数，则无解；
　　　　　　否则可把h[1]..h[N-1]都变成 h[N]，操作次数为(N-1) * (d-h[N])/2，此时d=h[N]；
　　　若h[N]>d 则无解（因为h[N]只能和h[N-1]一起变化）。