首页 > 代码库 > 湘潭大学OJ1202逆序数(归律)
湘潭大学OJ1202逆序数(归律)
题目描述
有n张卡片,分别标有数字1~n。有一天Silence把他们按某种序列排好,然后从第一张开始取出一张,再拿一张放到最后面,再取出一张,再拿出一张放到最后面...知道n张卡片全部取走。把取出的卡片按取出的顺序排好,正好是1,2,3,4,....,n。
现在,告诉你n,Silence希望你帮他计算原来的序列的逆序数。
例如,n=4时,原来的序列应该是1,3,2,4。这样,先取出卡片1,再把卡片3放到最后面,序列变成了2,4,3。再把2取出来,4放到后面,序列变成了3,4。再把3取出来,4放最后面,再把4取出来,这样取出卡片的顺序就是1,2,3,4了。那么原来序列(1,3,2,4)的逆序数是1.那么答案就是1啦。
输入
输入不超过1000个样例,每个样例一行,一个整数n(1 <= n <= 10^9)。
输出
每个样例输出一行,一个整数,为原来序列的逆序数
样例输入
4 99
样例输出
1 1631
Source
WW
#include<stdio.h> int main() { __int64 sum,n,k; while(scanf("%I64d",&n)>0) { sum=0; while(n>2) { k=(n+1)/2-1; sum+=(k+1)*k/2;//求和公式 n=n-(n+1)/2; if(n%2) n=n+1;//变成偶数,如果n为奇则当前这回只取出奇数个数 } printf("%I64d\n",sum); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。