11998: 【原1998】二哥买房

题目描述

author: qujun 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1998

题目描述

寂寞难耐的二哥想找个女朋友，当然二哥明白，作为没有房的卢瑟，女友这样的东西永远只会在梦中与他相会。所以呢，二哥决定弄套房子，买不起没关系，他可以自己盖！

二哥生活的世界是一维的，也就是一条无限长的数轴。他可以在数轴上的任意一点盖房子，在准备好材料要动工时，二哥发现了一个问题。

他平时有一些经常光顾的地方，比如某某餐馆、某某商场、某某女校等等。这些地方当然对应着这个数轴上的一个坐标，如果二哥盖的房子的坐标离这些坐标非常远的话，寂寞的二哥显然会非常困扰。

你知道二哥经常光顾的\(N\)个地方的坐标\(x_1,x_2,\dots,x_n\)，如果二哥把房子建在坐标\(P\)，那么二哥的困扰值为：\( \sum_{i=1}^{n}{\left\vert x_{i} - P \right\vert} \)

现在你需要帮二哥计算，他可能获得的最小的困扰值是多少。

注意，二哥可以在任意坐标盖房子，即使和某个经常光顾的地方重合也没关系。

输入格式

输入共有两行。

第一行一个正整数N。

第二行N个非负整数，表示\(x_1,x_2,\dots,x_n\)。

输出格式

一行，包含一个整数，表示二哥最小的困扰值。

数据范围

对于全部数据：N不超过100000，每个位置的坐标不超过10000。对于30%的数据，N不超过10。

样例输入

3
2 4 3

样例输出

限制

时间限制：500ms，内存限制：30000kb

ligongzzz's solution

#include "iostream"
#include "cmath"
#include "algorithm"
using namespace std;

int main() {
    int num;
    cin >> num;
    int *data = new int[num];
    for (int i = 0; i < num; i++)
        cin >> data[i];

    sort(data, data + num);
    int dis = 0;
    for (int i = 0; i < num;i++) {
        dis += abs(data[i] - data[num / 2]);
    }
    cout << dis;
    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

void quickSort(int *, int, int);

int main() {
    int n, *X, left = 0;
    int *counts;
    long long bestsum, sum = 0;
    cin >> n;
    int right = n, on = 0;
    int x0 = 0;

    X = new int[n];
    for (int i = 0; i < n; ++i) {
        cin >> X[i];
    }
    quickSort(X, 0, n - 1);

    counts = new int[X[n - 1] + 1];
    for (int i = 0; i < X[n - 1] + 1; i++) {
        counts[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        counts[X[i]] += 1;
    }

    for (int i = 0; i < X[n - 1] + 1; i++) {
        sum += counts[i] * i;
    }
    bestsum = sum;

    for (int i = 0; i < X[n - 1] + 1; i++) {
        left += on;
        on = counts[i];
        right -= counts[i];
        sum = sum + abs(i - x0) * left - abs(i - x0) * (right + on);
        if (bestsum > sum) {
            bestsum = sum;
        }
        x0 = i;
    }

    cout << bestsum;

    return 0;
}

void quickSort(int *s, int l, int r) {
    if (l < r) {
        int i = l, j = r, x = s[l];

        while (i < j) {
            while (i < j && s[j] >= x) {
                j--;
            }

            if (i < j) {
                s[i++] = s[j];
            }

            while (i < j && s[i] < x) {
                i++;
            }

            if (i < j) {
                s[j--] = s[i];
            }
        }
        s[i] = x;
        quickSort(s, l, i - 1);
        quickSort(s, i + 1, r);
    }
}

yyong119's solution

#include <cstdio>
#include <algorithm>
#define MAX_N 100010
using namespace std;
int a[MAX_N];
int cnt, n;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    sort(a, a + n);
    for (int i = 0; i < (n >> 1); ++i)
        cnt += a[n - 1 - i] - a[i];
    printf("%d\n", cnt);
    return 0;
}