题意:给定3个点,每次从两个端点(位置最小或位置最大)中挑选一个点进行移动,将其移动到原先两个端点之间的空位置上,直到3个点位置连续,问最少多少步,和最多多少步。
思路:
对于(x,y,z),x<y<z:
最多步数:
固定一端,一直选择另一端的端点移动。具体地,固定右端点,一直选择左端点进行移动,每次将左端点移动至最左边的空位置上(greedy),每一步这样的操作,消耗[x,y]区间中的一个空位置,直至用掉所有空位置;或者说每一次操作后,最新的[x1,y1]相对[x,y]长度减1,一直减到xn+2==yn。
故,最多的步数为,z-x-2。
最少步数:
若x+1=y,y+1=z,则需0步;
若y-x<=2或者z-y<=2,则需1步;
否则,需2步。
class Solution{public: vector numMovesStones(int a, int b, int c) { if(a>b) swap(a,b); if(a>c) swap(a,c); if(b>c) swap(b,c); //cout< <<" "<<<" "<<