首页 > 代码库 > XTU1202:逆序数

XTU1202:逆序数

题目描写叙述

有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

对于这道题,我仅仅想说
推吧。。

能够发现,奇偶一样的
1,2:  0
3,4:  1
5,6:  4
7,8:  7
9,10:  14
11,12:  19
13,14:  28

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll __int64

int main()
{
    ll n;
    while(~scanf("%I64d",&n))
    {
        LL ans=0;
        if(n%2==1) n++;
        while(n>2)
        {
            ans+=(n/2-1)*(n/2)/2;
            n=n/2;
            if(n%2) n++;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}




   

XTU1202:逆序数