HDU 多校赛2 Swaps and Inversions problem-6318
程序员文章站
2022-06-09 19:34:34
...
原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=6318
题意:本题就是求数列的逆序数然后用逆序数乘以min(x,y)这样才能使花费最少,求逆序数可以用归并,树状数组,暴力,暴力肯定会超时,一开始用树状数组不知道什么原因会一直WA,后来改用归并AC(由于粗心忘了初始化也WA了)
#include<stdio.h>
#include<string.h>
int a[100005], b[100005];
long long count;//记录逆序数
void merge(int low, int mid, int high)
{
int i = low, j = mid + 1, k = low;
while ((i <= mid) && (j <= high))
{
if (a[i] <= a[j])
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
count += mid - i + 1;//记录逆序数
}
}
while (i <= mid)
b[k++] = a[i++];
while (j <= high)
b[k++] = a[j++];
for (int i = low; i <= high; i++)
a[i] = b[i];
}
void sort(long long low, long long high)
{
int mid = (low + high) / 2;
int x, y, z;
if (low >= high)
return;
sort(low, mid);
sort(mid + 1, high);
merge(low, mid, high);
return;
}
int main()
{
int n,x,y;
while (~scanf("%d %d %d", &n, &x, &y)) {
count = 0;//这个初始化不能少
for (int i = 0; i<n; i++)
scanf("%d", &a[i]);
sort(0, n - 1);
//printf("%lld\n", count);
if(y<x)
printf("%lld\n", count*y);
else
printf("%lld\n", count*x);
}
return 0;
}
关于求逆序数的算法这里有大佬的博客
归并:https://blog.csdn.net/zangker/article/details/42217909
树状数组:https://blog.csdn.net/cattycat/article/details/5640838
下一篇: ajax传递json时为什么会出现乱码