一排杯子共2N只,左边N只满杯,右边N只空杯,使这排杯子变成满杯与空杯相互交错,最少要移动多少对杯子?

Question

一排杯子共2N只,左边N只满杯,右边N只空杯,使这排杯子变成满杯与空杯相互交错,最少要移动多少对杯子?

Answer 1

n为偶数时,为n/2,n为奇数时,为(n-1)/2
水可以倒.从满到空,被倒的杯子不算
例.n为5时
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
■■■■■□□□□□--->■□■□■□■□■□
很简单,只要拿起第二只杯子,把里面的汽水倒进第七只杯子,再拿起第四只杯子,把里面的汽水倒入第九只杯子就行了
如果有2n只杯子,n只满杯,n只空杯,需要将[n/2]对杯子互换位置,方法是2k号杯子与2k+n号杯子互换位置即可(k=1,2,3,...)若n=100,则需互换50次