HDU-杭电多校2018联合训练第二场 Swaps and Inversions(树状数组求逆序对)
程序员文章站
2022-06-09 19:27:20
...
Swaps and Inversions
题意:
给你N,X,Y三个整数<=1e5 ,再给你N个整数。
问你交换两个数的代价是花费Y元。
最后逆序对的个数花费X元。所以他问你的是:怎么花费最小。
题解:
其实两两相邻交换就暗示了什么??这不就是求逆序数的总数吗?
数据大不能维护就需要进行离散化。
但是注意!!!记得,不仅要把大小排序,还需要把序号排序。不然会WA(WA多次得出的教训)
#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;
}