本文共 1373 字，大约阅读时间需要 4 分钟。

题意：

给出一个数列，其中每有一个逆序数就花费x元，也可以花费y元交换相邻两个数，求处理这个数列的最小花费

思路：

可分析出，交换一次最多只能减少一个逆序数，所以只可能全部交换或者一个都不交换，故此题只需求出逆序数个数即可

代码：

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N=100050;int n;long long c[N];      //c[n]表示a[1~n]的和，a数组省略struct node{    int val,pos;}a[100005];int lowbit(int x)       //求2^k{    return x & -x;}long long getsum(int n)   //区间查询，求a[1~n]的和{    long long res = 0;    while(n>0)    {        res+=c[n];        n=n-lowbit(n);    }    return res;}int change(int x)  //单点更新，将c[x]的值加1{     while(x<=n)     {         c[x]++;         x+=lowbit(x);     }}bool cmp(node a,node b)         //包含相同数{    if(a.val!=b.val)        return a.val>b.val;    return a.pos>b.pos;}int main(){    std::ios::sync_with_stdio(false);    int x,y;    while(cin>>n>>x>>y)    {        memset(c,0,sizeof(c));        for(int i=1;i<=n;i++)        {            cin>>a[i].val;            a[i].pos=i;        }        sort(a+1,a+n+1,cmp);        long long cnt=0;        for(int i=1;i<=n;i++)        {            change(a[i].pos);                     //修改最大数位置的值            cnt+=getsum(a[i].pos-1);     //最大数位置之前的所有位置和，即区间求和，可知比当前数小的数有多少个        }        long long ans1=cnt*x;        long long ans2=cnt*y;        cout<
      
       <