HDU 1394 树状数组

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct t
{
    int id,num;
}s[5001];
int b[5001];
int tree[5001],n;
bool cmp(t a,t b)
{
    return a.num<b.num;
}
int Lowbit(int x)
{
    return x&(-x);
}
void update(int x)
{
    for(int i=x;i>0;i-=Lowbit(i))
    {
        tree[i]++;
    }
}
int Getsum(int x)
{
    int temp=0;
    for(int i=x;i<=n;i+=Lowbit(i))
    {
        temp+=tree[i];
    }
    return temp;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
             scanf("%d",&s[i].num);
             s[i].id=i;
        }
        sort(s+1,s+n+1,cmp);
        b[s[1].id]=1;
        for(int i=2;i<=n;i++)
        {
            if(s[i].num!=s[i-1].num)
                   b[s[i].id]=i;
            else
                   b[s[i].id]=b[s[i-1].id];
        }
        for(int i=1;i<=n;i++)
        {
            cnt+=Getsum(b[i]);
            update(b[i]);
        }
        int min=cnt;
        for(int i=1;i<=n;i++)
        {
           int ma=b[i]-1;//比它小的
           int mb=n-b[i];//比它大的
           cnt=cnt+mb-ma;
           if(cnt<min)  min=cnt;
        }
        printf("%d/n",min);
    }
    return 0;
}

最后

以上就是勤劳康乃馨为你收集整理的HDU 1394 树状数组的全部内容，希望文章能够帮你解决HDU 1394 树状数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。