Skip to content

11258: 【原1258】圣诞树2

题目

题目描述

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

Description

Dunphy一家制作了很多圣诞树，他们把这些树排成一排。他们发现这些数的高度参差不齐，他们现在希望知道这一排树的“不和谐度”。“不和谐度”指的是一共有多少对树使排在前面的树高于排在后面的树。

例如共有5棵树排成一排，它们的高度分别为5 2 7 2 10，则不和谐度为3。不和谐的3对树是第一棵和第二棵，第一棵和第四棵，第三棵和第四棵。

Input Format

第一行为n，表示共n棵树。 接下来一行有n个不超过100000正整数，依次表示排成一排的每棵树的高度。先输入的排在前面。

有60%的数据n<=1000。 对于100%的数据n<=100000。

Output Format

输出一个正整数k，表示不和谐度。

Sample Input

5
5 2 7 2 10

Sample Output

3

BugenZhao's solution 

//
// Created by BugenZhao on 2019/5/16.
//

#ifndef SBL_BMERGESORT_H
#define SBL_BMERGESORT_H

template<typename Item>
class BMergeSort {
public:
    static long long ans;

private:
    static bool less(Item v, Item w) {
        return v < w;
    }

    static void doSort(Item *a, int lo, int hi, Item *aux) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo - 1) / 2;
        doSort(a, lo, mid, aux);
        doSort(a, mid + 1, hi, aux);
        merge(a, lo, mid, hi, aux);
    }

    static void merge(Item *a, int lo, int mid, int hi, Item *aux) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = a[i];
        }
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
                // caution: <=
            else if (!less(aux[j], aux[i])) a[k] = aux[i++];
            else a[k] = aux[j++], ans += mid - i + 1;
        }
    }

public:
    static void sort(Item *a, int n) {
        sort(a, 0, n - 1);
    }

    static void sort(Item *a, int lo, int hi) {
        Item *aux = new Item[hi - lo + 1];
        doSort(a, lo, hi, aux);
        delete[] aux;
    }
};

template<typename Item>
long long BMergeSort<Item>::ans = 0;

#endif //SBL_BMERGESORT_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    auto a = new int[k];
    for (int i = 0; i < k; ++i) {
        cin >> a[i];
    }
    BMergeSort<int>::sort(a, k);
    cout << BMergeSort<int>::ans << endl;
    delete[] a;
    return 0;
}

ligongzzz's solution 

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

class node {
public:
    int val = 0;
    int left = 0, right = 0;
};

int val_data[100009] = { 0 };
node smt[400009];

void build_tree(int l, int r, int root) {
    smt[root].left = l;
    smt[root].right = r;
    if (l == r - 1) {
        smt[root].val = val_data[l];
        return;
    }

    int mid = (l + r) >> 1;
    build_tree(l, mid, root * 2);
    build_tree(mid, r, root * 2 + 1);

    smt[root].val = smt[root * 2].val + smt[root * 2 + 1].val;
}

int query(int l, int r, int root) {
    if (l <= smt[root].left && smt[root].right <= r) {
        return smt[root].val;
    }

    auto mid = (smt[root].left + smt[root].right) >> 1;
    int ans = 0;
    if (l < mid) {
        ans += query(l, r, root * 2);
    }
    if (r > mid) {
        ans += query(l, r, root * 2 + 1);
    }
    return ans;
}

void update(int val,int pos, int root) {
    if (smt[root].right - smt[root].left == 1) {
        smt[root].val += val;
        return;
    }

    auto mid = (smt[root].left + smt[root].right) >> 1;
    if (pos < mid) {
        update(val, pos, root * 2);
    }
    else {
        update(val, pos, root * 2 + 1);
    }
    smt[root].val = smt[root * 2].val + smt[root * 2 + 1].val;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    build_tree(0, 100009, 1);

    long long cnt = 0;
    for (int i = 0; i < n; ++i) {
        cin >> val_data[i];

        update(1, val_data[i], 1);
        cnt += (long long)query(val_data[i] + 1, 100009, 1);
    }

    cout << cnt;

    return 0;
}

Neight99's solution 

#include <iostream>

using namespace std;

long long sum = 0, trees[100100], newTrees[100100];
int n;

void cal(int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> trees[i];
    }

    cal(0, n - 1);

    cout << sum;

    return 0;
}

void cal(int l, int r) {
    int mid = (l + r) / 2;
    int i, j, tmp;

    if (r > l) {
        cal(l, mid);
        cal(mid + 1, r);
        tmp = l;

        for (i = l, j = mid + 1; i <= mid && j <= r;) {
            if (trees[i] > trees[j]) {
                newTrees[tmp++] = trees[j++];
                sum += mid - i + 1;
            } else {
                newTrees[tmp++] = trees[i++];
            }
        }
        if (i <= mid) {
            for (; i <= mid;) {
                newTrees[tmp++] = trees[i++];
            }
        }

        if (j <= r) {
            for (; j <= r;) {
                newTrees[tmp++] = trees[j++];
            }
        }

        for (i = l; i <= r; i++) {
            trees[i] = newTrees[i];
        }
    }
}

skyzh's solution

//
// Created by 3t on 2019/5/16.
//

#include <iostream>

using namespace std;

static int MERGE_TMP[200000];

long long ans = 0;

void merge(int *x, int mid, int N) {
    int i = 0, j = mid;
    int k = 0;
    while (i < mid && j < N) {
        int _x = x[i];
        int _y = x[j];
        if (_x <= _y) {
            MERGE_TMP[k++] = _x;
            i++;
        } else {
            ans += mid - i;
            MERGE_TMP[k++] = _y;
            j++;
        }
    }
    while (i < mid) {
        MERGE_TMP[k++] = x[i++];
    }
    while (j < N) {
        MERGE_TMP[k++] = x[j++];
    }
    for (int i = 0; i < k; i++) {
        x[i] = MERGE_TMP[i];
    }
}

void merge_sort(int *x, int N) {
    if (N == 1) return;
    if (N == 2) {
        if (x[0] > x[1]) {
            ++ans;
            swap(x[0], x[1]);
        }
        return;
    }
    int mid = N / 2;
    merge_sort(x, mid);
    merge_sort(x + mid, N - mid);
    merge(x, mid, N);
}

int X[100000];
int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &X[i]);
    }
    merge_sort(X, N);
    cout << ans << endl;
    return 0;
}

yyong119's solution 

#include <cstdio>
using namespace std;
const int MAX_N = 100010;
long long ans;
int n;
int a[MAX_N];

void merge(int l, int r) {

    int mid = (l + r) >> 1, i = l, j = mid + 1, k = l;
    int tmp[MAX_N];
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            ans += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int i = l; i <= r; ++i) a[i] = tmp[i];
}

void mergesort(int l, int r) {

    if (l == r) return;
    int mid = (l + r) >> 1;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    merge(l, r);
}

int main() {

    // ios::sync_with_stdio(false);
    // cin >> n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) //cin >> a[i];
        scanf("%d", &a[i]);
    mergesort(1, n);
    // cout << ans << endl;
    printf("%lld\n", ans);
    return 0;
}