# 11571: 【原1571】最小花费

### 题目描述

author: lwher 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1571 ﻿# Description 土豪李老板买了两包砖石，每包砖石各有N颗，每个砖石各有一个价值。现在李老板将每包砖石都排成一排，且同一排砖石的价值互不相同。

## Sample Input

``````4
2 3 1 4
3 2 1 4
``````

## Sample Output

``````1
``````

## Sample Input

``````4
1 3 4 2
1 7 2 4
``````

## Sample Output

``````2
``````

## Limits

• 对于\(10\%\)的数据，1<= N <= 10。
• 对于\(30\%\)的数据，1<= N <= 100。
• 对于\(60\%\)的数据，1<= N <= 1000。
• 对于\(100\%\)的数据，1 <= N <= 100000, 0 <= 砖石价值 <= 2^31-1。

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cmath"
using namespace std;

long long myMergeSort(int *data, int num) {
if (num == 0) return 0;
else if (num == 1) return 0;

long long result = 0;
result += myMergeSort(data, num / 2);
result += myMergeSort(data + num / 2, num - num / 2);

//合并
int *temp = new int[num];

for (int i = 0, j = num / 2, n = 0; i < num / 2 || j < num;n++) {
if (i < num / 2 && j < num) {
if (data[i] < data[j]) {
temp[n] = data[i];
i++;
result += j-num/2;
}
else {
temp[n] = data[j];
j++;
}
}
else if (i == num / 2) {
temp[n] = data[j];
j++;
}
else if (j == num ) {
temp[n] = data[i];
i++;
result += j-num/2;
}
}

//复制
for (int i = 0; i < num; i++)
data[i] = temp[i];

delete temp;
return result;
}

long long myMergeSort(int *data,int *datab,int num) {
if (num == 0) return 0;
else if (num == 1) return 0;

long long result = 0;
result += myMergeSort(data,datab, num / 2);
result += myMergeSort(data + num / 2,datab+num/2, num - num / 2);

//合并
int *temp = new int[num];
int *tempb = new int[num];

for (int i = 0, j = num / 2, n = 0; i < num / 2 || j < num; n++) {
if (i < num / 2 && j < num) {
if (data[i] < data[j]) {
temp[n] = data[i];
tempb[n] = datab[i];
i++;
result += j - num / 2;
}
else {
temp[n] = data[j];
tempb[n] = datab[j];
j++;
}
}
else if (i == num / 2) {
temp[n] = data[j];
tempb[n] = datab[j];
j++;
}
else if (j == num) {
temp[n] = data[i];
tempb[n] = datab[i];
i++;
result += j - num / 2;
}
}

//复制
for (int i = 0; i < num; i++) {
data[i] = temp[i];
datab[i] = tempb[i];
}

delete temp;
delete tempb;
return result;
}

int a[100009], b[100009],aList[100009],bList[100009],temp[100009];

int main() {
int num;
cin >> num;

for (int i = 0; i < num; i++) {
scanf("%d", &a[i]);
aList[i] = i;
}
for (int i = 0; i < num; i++) {
scanf("%d", &b[i]);
bList[i] = i;
}

//排序
myMergeSort(a, aList, num);
myMergeSort(b, bList, num);

//按情况排序
for (int i = 0; i < num; i++) {
temp[bList[i]] = aList[i];
}

//再排序
cout << myMergeSort(temp, b, num)%99999997;

return 0;
}
``````

## Neight99's solution

``````#include <algorithm>
#include <iostream>

using namespace std;

struct Node {
int pos;
int data;
};

bool cmp(Node, Node);

int Low(int);

void plus1(int);

int sum1(int);

Node A[100010], B[100010];
int c[100010], d[100010], N, ans;
int main() {
cin >> N;
for (int i = 1; i < N + 1; i++) {
cin >> A[i].data;
A[i].pos = i;
}
for (int i = 1; i < N + 1; i++) {
cin >> B[i].data;
B[i].pos = i;
}

sort(A + 1, A + N + 1, cmp);
sort(B + 1, B + N + 1, cmp);

for (int i = 1; i < N + 1; i++) {
d[A[i].pos] = B[i].pos;
}

for (int i = N; i > 0; i--) {
plus1(d[i]);
ans = (ans + sum1(d[i] - 1)) % 99999997;
}

cout << ans % 99999997;

return 0;
}

bool cmp(Node x, Node y) { return x.data < y.data; }

int Low(int x) { return x & (-x); }

void plus1(int x) {
for (int i = x; i < N + 1; i += Low(i)) {
c[i]++;
}
return;
}

int sum1(int x) {
int sum = 0;
for (int i = x; i != 0; i -= Low(i)) {
sum = (sum + c[i]) % 99999997;
}

return sum % 99999997;
}

/*void sort(Node *N,int a,int b) {
if(a>b) {
return;
} else {
int first = a, last = b;
Node n = N[first];

while (first < last) {
while (first < last && !cmp(N[last], n)) {
last--;
}

N[first] = N[last];

while (first < last && cmp(N[last], n)) {
first++;
}

N[last] = N[first];
}
N[first] = n;
sort(N, a, first - 1);
sort(N, first + 1, b);
}
for(int i=a;i<b-1;i++) {
for(int j=a;j<b-i-1;j++) {
Node tmp;
if(cmp(N[j],N[j+1])!=0) {
tmp=N[j];
N[j]=N[j+1];
N[j+1]=tmp;
}
}
}
}*/
``````