动态规划，不断地把人群划分成两半，左边的走左边道，右边走右边道最近，进行交换

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int[] dp=new int[32767];
        dp[1]=0;
        dp[2]=1;
        dp[3]=3;
        for(int i=4;i<32767;i++) {//把人群划分成两半进行交换
        	if(i%2==0) {//偶数个人
        		dp[i]=dp[i/2]+dp[i/2];
        	}else {//奇数个人
        		dp[i]=dp[i/2]+dp[i/2+1];
        	}
        }
        while(n-->0) {
        	int m=scanner.nextInt();
        	System.out.println(dp[m]);
        }
    }
}