欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU-杭电多校2018联合训练第二场 Swaps and Inversions(树状数组求逆序对)

程序员文章站 2022-06-09 19:27:20
...

Swaps and Inversions

题意:

给你N,X,Y三个整数<=1e5 ,再给你N个整数。

问你交换两个数的代价是花费Y元。

最后逆序对的个数花费X元。所以他问你的是:怎么花费最小。

题解:

其实两两相邻交换就暗示了什么??这不就是求逆序数的总数吗?

POJ 2299 逆序数模板题

数据大不能维护就需要进行离散化。

但是注意!!!记得,不仅要把大小排序,还需要把序号排序。不然会WA(WA多次得出的教训)

HDU-杭电多校2018联合训练第二场 Swaps and Inversions(树状数组求逆序对)

#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100050 ;
typedef long long ll;
typedef struct node{
    ll val,No;
}node ;
node a[N];
ll c[N],n;
int cmp(node a,node b){
    if(a.val==b.val){
        return a.No<b.No;        //没有这个判断WA
    }
    return a.val<b.val;
}
ll lowbit(ll x){
    return x&(-x);
}
ll getsum(ll x){
    ll ret=0;
    for(; x>0;ret+=c[x],x-=lowbit(x));
    return ret;
}
void update(ll x,ll val){
    for(;x<=n;c[x]+=val,x+=lowbit(x));
}
int main()
{
    ll x,y;
    while(~scanf("%lld%lld%lld",&n,&x,&y)){
        memset(c,0,sizeof(c));
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i].val);
            a[i].No=i;           //记录原来的下标
        }
        int aa[N]={0};
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++){
            aa[a[i].No]=i;       //把原来的下标附上值(离散后的大小关系顺序)
        }
        ll sum=0;
        for(int i=1;i<=n;i++){
            update(aa[i],1);     //对aa[i]这个位置进行维护
            sum+=(i-getsum(aa[i])); //逆序数=当前位置- 前面多少个比自己小的                 
        }
        //printf("%lld\n",sum);
        ll ans=sum*min(x,y);
        printf("%lld\n",ans);
    }
    return 0;
}

 

相关标签: 多校HDU2018第二场