首页 > 代码库 > Uva 1315 - Creaz tea party ( 数学 + 规律 )
Uva 1315 - Creaz tea party ( 数学 + 规律 )
Uva 1315 - Creaz tea party ( 数学 + 规律 )
题意： 一个环，围在一个坐了N个人。每次操纵可以交换相邻的两个人的位置。求最少需要交换几次，可以变为逆序。
这里的逆序指的是原来在A左边的人在A的右边，在A右边的在A的左边。
分析：
如果是线性的，，，果断类似冒牌排序(n)(n-1)/2
但是这里是环，推了推但是推不出结果。。结论是将环分为两段线性的序列，线性的满足上面的公式。
如: 1 2 3 4 5
线性: 5 4 3 2 1 ( 10次 )
环状: 3 2 1 5 4 ( 4次 ) -----------> 相当于 1 2 3做线性 ， 4 5 也做线性。。至于为什么从中间开始，不会证明。
/* ***********************************************ID : whiteblock63LANG : G++PROG : Uva 1315 - Creaz tea party DATE : 2014-10-08 18:07:47************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define CLR( a, b ) memset( a, b, sizeof(a) )using namespace std;int t, n;/*无环情况类似于冒泡排序---耗时为n(n-1)/2这里有环，有环的情况，例如 1 2 3 4 5化为 5 4 3 2 1 ----需要交换10次，并不是最优化为 3 2 1 5 4 ----需要交换4次，最优可以想到把 环分解为两条链，自然是中间切开会是最优。注意讨论奇偶就行了。*/int main(){ scanf( "%d", &t ); while( t-- ) { scanf( "%d", &n ); if( n & 1 ) { n = n/2 + 1; printf( "%d\n", n*(n-1)/2 + (n-1)*(n-2)/2 ); } else { n /= 2; printf( "%d\n", n*(n-1)); } } return 0;}
Uva 1315 - Creaz tea party ( 数学 + 规律 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。