HDU 6318 Swaps and Inversions(归并排序 || 树状数组)题解

题意:一个逆序对罚钱x元,现在给你交换的机会,每交换任意相邻两个数花钱y,问你最少付多少钱

思路:最近在补之前还没过的题,发现了这道多校的题。显然,交换相邻两个数逆序对必然会变化+1或者-1,那我们肯定是-1操作。那么显然问题就变成了求逆序对数*min(x,y)。树状数组求逆序对数。

代码:

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = + ;
const int seed = ;
const ll MOD = ;
const int INF = 0x3f3f3f3f;
int a[maxn], b[maxn], node[maxn];
int lowbit(int x){
return x&(-x);
}
void update(int x){
for(int i = x; i < maxn; i += lowbit(i))
node[i]++;
}
ll query(int x){
ll ret = ;
for(int i = x; i > ; i -= lowbit(i))
ret += node[i];
return ret;
}
int main(){
int n, x, y;
while(~scanf("%d%d%d", &n, &x, &y)){
ll ans = ;
memset(node, , sizeof(node));
for(int i = ; i <= n; i++)
scanf("%d", &a[i]), b[i] = a[i];
sort(b + , b + n + );
for(int i = ; i <= n; i++)
a[i] = lower_bound(b + , b + n + , a[i]) - b;
for(int i = n; i >= ; i--){
ans += query(a[i] - );
update(a[i]);
}
printf("%lld\n", min(x, y) * ans);
}
return ;
}
上一篇:可视化库-Matplotlib基础设置(第三天)


下一篇:python 可视化库