题意:有编号为1~n的人顺时针围成一圈坐在一起,相邻的两个人交换位置需要花费的时间为1,现在想使得编号为1~n的人逆时针坐在一起,所需要花费的最少时间是多少。
题解:首先考虑线性组合,即1~n排成一条线,这时所需要花费的时间为n * (n-1)/ 2。如果是一个环的话1-2-3-4-5变成2-1-5-4-3也是合法的,这样就可以想到枚举编号为n的最终的位置,
左右两边的时间花费为m * (m-1)/ 2(m为人数且有序),所以编号为n的人在中间的时候总花费最少。
即n为奇数ans = (n - 1) * (n - 1) / 4;否则ans = (n / 2 - 1) * n / 2。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> using namespace std; int n; int main() { int cas; scanf("%d",&cas); while(cas--) { scanf("%d",&n); int ans; if(n & 1) ans = (n - 1) * (n - 1) / 4; else ans = (n / 2 - 1) * n / 2; printf("%d\n",ans); } return 0; }