hdu 5122(2014ACM/ICPC亚洲区北京站) K题 K.Bro Sorting

传送门

对于错想成lis的解法，提供一组反例
1 3 4 2 5
同时对于这次案例也可以观察出解法：
对于每一个数，如果存在比它小的数在它后面,它势必需要移动，因为只能小的数无法向右移动，而且每一次移动都必然可以使得这个数到达正确位置，这是根据题意而得的

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000LL

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N=1e6+10;

const int Max=1e6+5;

int a[N],c[N];

int lowbit(int x){

   return x&(-x);

}

void add(int x,int d){

    while(x<Max){

        c[x]+=d;

        x+=lowbit(x);

    }

}

int sum(int x){

    int ret=0;

    while(x>0){

        ret+=c[x];

        x-=lowbit(x);

    }

    return ret;

}

int main()

{

    int T,ca=0;

    for(T=read();T;T--){

        int n=read(),x;

        memset(c,0,sizeof(c));

        for(int i=1;i<=n;i++){

            a[i]=read();

        }

        int ans=0;

        for(int i=n;i>=1;i--){

            if(sum(a[i]-1)>0) ans++;

            add(a[i],1);

        }

        printf("Case #%d: %d\n",++ca,ans);

    }

    return 0;

}

巴特西

hdu 5122(2014ACM/ICPC亚洲区北京站) K题 K.Bro Sorting

传送门

最新文章

热门文章