题目链接http:acm.hdu.edu.cnshowproblem.php?pid6318【题意】’给你一个长度为n的序列序列中每存在一个逆序对就会产生x的代价6318 【题意】 ’给你一个长度为n的序列序列中每存在一个逆序对就
【题意】 ’给你一个长度为n的序列序列中每存在一个逆序对就会产生x的代价你也可以交换序列中相邻的元素来消除一些逆序对交换一次的代价为y求怎样操作使得序列最终产生的代价最小
【输入格式】 多组输入第一行为n,x,yn,x,y<1e5代表序列长度和两种不同的代价第二行为n个整数每个整数的范围是[-1e9,1e9]代表序列中的每个值。
【输出格式】 对每组数据输出最小代价是多少
【思路】 对于任意一个序列交换多少次相邻元素就会消除多少对原有的逆序对所以只要计算出逆序对的个数再乘以min{x,y}即可求逆序对可以用归并排序或树状数组但要在之前对数据离散化一下。
#includeusing namespace std;typedef long long ll;const int maxn100050;ll n,x,y;ll a[maxn],c[maxn];ll bit[maxn];void add(int i,ll x){while(i