学步园

HDU 5122

2014北京站 J题

题意:  给你一个1~N序列   随机选一个数 sort(向上交换 直到要交换的数比他大)

问: 最好的情况要sort几次 才能变为升序列

大的 在后面的 肯定要先换  不然就会档着后面的数

所以用树状数组逆序插入  插入之前先查找 如果出现了比他小的数就ans++

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e6+10;

int B[MAXN],A[MAXN];
inline int lowbit(int x)
{
    return x&-x;
}

inline void ins(int pos,int n)
{
    for(;pos<=n;pos+=lowbit(pos))
        A[pos]++;
}

inline int find(int pos)
{
    for(;pos;pos-=lowbit(pos))
        if(A[pos])
            return 1;
    return 0;
}

int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&B[i]);

        reverse(B,B+n);
        memset(A,0,sizeof(A));

        int sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=find(B[i]);
            ins(B[i],n);
        }
        printf("Case #%d: %d\n",cas++,sum);
    }
}

---------------------------------------水平线------------------------------------------

最近的感觉自己手残眼贱啊...  哈理工比赛看错题  递推都能写残 -  -