Swaps and Inversions
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1662 Accepted Submission(s): 615
Problem Description
Long long ago, there was an integer sequence a.
Tonyfang think this sequence is messy, so he will count the number of inversions in this sequence. Because he is angry, you will have to pay x yuan for every inversion in the sequence.
You don't want to pay too much, so you can try to play some tricks before he sees this sequence. You can pay y yuan to swap any two adjacent elements.
What is the minimum amount of money you need to spend?
The definition of inversion in this problem is pair (i,j) which 1≤i<j≤n and ai>aj.
Input
There are multiple test cases, please read till the end of input file.
For each test, in the first line, three integers, n,x,y, n represents the length of the sequence.
In the second line, n integers separated by spaces, representing the orginal sequence a.
1≤n,x,y≤100000, numbers in the sequence are in [−109,109]. There're 10 test cases.
Output
For every test case, a single integer representing minimum money to pay.
Sample Input
3 233 666
1 2 3
3 1 666
3 2 1
Sample Output
3
題意：
n --> 序列的長度
x --> 序列中每存在一對逆序對所需要支付的代價
y --> 每交換一次相鄰的兩個數所需要支付的代價
輸出所需最小代價
比如第二組資料：有3、2、1 長度為3的序列，初始逆序對為3，因為隻有3組逆序對，且存在一對逆序對的代價為1 ，交換1次代價為666，明顯3小于666，是以最後答案為3。
題解：
很容易得出每一次交換可以減少一對逆序對，是以我們設逆序對數為 cnt，交換次數為 k，設所需代價ans。
得出公式，ans = (cnt-k)*x + k*y。化簡得 ans = (y-x)*k + cnt*x。我們得出兩個未知數cnt 和 k。隻要把cnt 逆序對數求出，k就求出了。
是以先要解決求逆序對問題。
有兩種解法：1、離散化+樹狀數組 2、歸并排序
這裡我選擇了用歸并排序，有需要的自己看看，借用大佬的部落格。
求出cnt 後，得出0 <= k <= cnt。是以此時ans就變成一個很簡單的函數 (y = k*b+c)。
可以發現，兩個都是單調函數，是以隻要看x,y那個更大就行最終答案就是ans * min(x,y)。
代碼
#include <stdio.h>
#define ll long long
ll c = 0; //用來記逆序對數
// 合并兩個有序的數組 mergeArrary
void mergeArrary(ll a[], ll first, ll mid, ll last, ll temp[]){
ll i = first, j = mid+1;
ll n = mid, m = last;
ll k = first;
while (i <= n && j <= m){
if (a[i] <= a[j]) temp[k++] = a[i++];
else {
temp[k++] = a[j++];
c += j-k; //記錄逆序對的核心，手算一遍就會明白其中的妙處
}
}
while (i <= n) temp[k++] = a[i++];
while (j <= m) temp[k++] = a[j++];
for (int i = first; i < k; i++){
a[i] = temp[i]; //更新原數組
}
}
// 歸并算法，遞歸
void mergeSort(ll a[], ll first, ll last, ll temp[]){
if (first < last){
ll mid = (first+last) / 2;
mergeSort(a, first, mid, temp);
mergeSort(a, mid+1, last, temp);
mergeArrary(a, first, mid, last, temp);
}
}
int main(){
ll n,x,y;
while (scanf("%lld %lld %lld",&n,&x,&y) != EOF){
ll a[100005],t[100005];
for (ll i = 0; i < n; i++){
scanf("%lld",&a[i]);
}
c = 0;
mergeSort(a, 0, n-1, t);
if (x < y)
printf("%lld\n",c*x);
else
printf("%lld\n",c*y);
}
}
還有就是要開long long 資料挺大的