树状数组 hdu2689 hdu2838

快来打我* 2021-11-01 03:38 312阅读 0赞

题意：给定一个正整数n，和一个1-n的一个排列，每个数可以和旁边的两个数的任意一个交换，每交换一次总次数就要加一，问将这个排列转换成一个递增的排列需要多少次交换？

题意可以转换成求这个排列的逆序对数。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int M=1e3+3;
    int bit[M],n;
    void update(int x,int c){
        while(x<=n)
            bit[x]+=c,x+=x&-x;
    }
    int sum(int x){
        int ans=0;
        while(x)
            ans+=bit[x],x-=x&-x;
        return ans;
    }
    int main(){
        while(~scanf("%d",&n)){
            int ans=0;
            memset(bit,0,sizeof(bit));
            for(int i=1;i<=n;i++){
                int x;
                scanf("%d",&x);
                update(x,1);
                ans+=i-sum(x);//sum(x)表示小于等于x的总数，而i-sum()则表示大于x的总数，即为逆序数的总数
            }
            printf("%d\n",ans);
        }
        return 0;
    }

2838

题意：给定一序列，问排成升序所要求的最少代价，序列中俩俩可相交换，代价为俩者的和

分析：

对于每个数字x，我们只需要把它和前面比它大的数字交换，求出交换代价，重复执行就能得出答案。

这个代价就是，比它大的数字个数t\*x+前面比它大的数字和。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int M=1e5+5;
    ll cnt[M],sum[M],n;
    void update(int x,int c1,int c2){
        while(x<=n){
            cnt[x]+=c2;
            sum[x]+=c1;
            x+=x&-x;
        }
    }
    ll cntt(int x){
        ll ans=0;
        while(x)
            ans+=cnt[x],x-=x&-x;
        return ans;
    }
    ll summ(int x){
        ll ans=0;
        while(x)
            ans+=sum[x],x-=x&-x;
        return ans;
    }
    int main(){
        while(~scanf("%d",&n)){
            for(int i=0;i<=n;i++)
                cnt[i]=0,sum[i]=0;
            ll ans=0;
            for(int i=1;i<=n;i++){
                int x;
                scanf("%d",&x);
                update(x,x,1);
                ans+=(i-cntt(x))*1ll*x*1ll+summ(n)-summ(x);
            }
            printf("%I64d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/starve/p/11182274.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/e3d327a8a1224ae2bb31efb3040433de.png