hdu1214 圆桌会议

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1214

HDU ACM集训队的队员在暑假集训时经常要讨论自己在做题中遇到的问题.每当面临自己解决不了的问题时,他们

就会围坐在一张圆形的桌子旁进行交流,经过大家的讨论后一般没有解决不了的问题,这也只有HDU ACM集训队特

有的圆桌会议,有一天你也可以进来体会一下哦:),在一天在讨论的时候,Eddy想出了一个极为古怪的想法,如果他们

在每一分钟内,一对相邻的两个ACM队员交换一下位子,那么要多少时间才能得到与原始状态相反的座位顺序呢?(即

对于每个队员，原先在他左面的队员后来在他右面，原先在他右面的队员在他左面),这当然难不倒其他的聪明的其

他队友们,马上就把这个古怪的问题给解决了,你知道是怎么解决的吗?

　　首先我们不难想到，让一个不动，第二个去第n个位置，移动n-2次，然后第3个（此时在第二个位置）去第n-1个位置，移动n-3次。。。这样移动下来一共需要（n-1）*（n-2）/2次，发现过不了样例，忧伤~

　　而对于直线型的桌子，第一个就必须得到最后一个去才能实现逆序，所以最终需要移动的就是n*（n-1）/2次，这样我们发现挨个移动到相应位置的确是最优的方案，但是我们这样移动到底冤枉路走在了哪里那？读题我们会发现，虽然最后要求逆序，但每个人坐在哪里是没有硬性要求的，毕竟是圆形桌子，那么，我们把n个人平均分成两部分，每部分各自移动比如12345 让12变成21需要一次，345变成543需要3次，这样就变成了21543，符合要求，并且运用了一次二分一样的思想把次数降了下去（真神奇）

代码：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n;

 int n1;

 int ans;

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         ans=;

         n1=n/;

         n-=n1;

         ans+=(n1*(n1-))/;

         ans+=(n*(n-))/;

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

hdu1214 圆桌会议

最新文章

热门文章