11571: 【原1571】最小花费

题目描述

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

有一天李老板和人赌钱，他们认为这两包砖石的价值差距可以定义为sigma(Ai - Bi)^2，其中Ai,Bi分别表示第一、第二包砖石排在第i位的砖石，他们根据随机排列的两包砖石价值差距的大小来判断输赢。

李老板经过思考，他打算买小，但他又觉得不稳健，于是他打算贿赂排砖石的人。排砖石的人每次可以交换相邻两颗砖石，李老板希望那个人通过若干次交换使得砖石价值差距最小，现在问最少要交换几次。

如果答案太大，请输出这个答案对99,999,997取模的结果。

李老板：这题如果不会做，也可以随时来找我。

Input Format

第一行有一个整数N ，代表每包砖石的个数。

第二行 N 个数代表李老板买的第一包砖石的价值{X_1,X_2,…,X_N}。

第三行 N 个数代表李老板买的第二包砖石的价值{Y_1,Y_2,…,Y_N}。

Output Format

一个整数，即李老板想要的答案。

Sample Input

4
2 3 1 4
3 2 1 4

Sample Output

Sample Input

4
1 3 4 2
1 7 2 4

Sample Output

样例1说明

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

样例2说明

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 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;
            }
        }
    }
}*/