题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2838

题解:

给你N个排列不规则的数,任务是把它从小到大排好,每次只能交换相邻两个数,交换一次的代价为两数之和,求最小代价。

每头牛的暴力值是唯一的。首先,我们看到数据范围10W,暴力的话,O(N^2)必挂,然后我们想到了树状数组思路:对某个下标k,先求逆序对ans,然后已知k和前面的逆序数要两两交换,所以对于本次的k,交换的总值为v+k*ans,val是前面超了的值之和。

/*
 * Author: Haipz
 * School: HDU
 * File Name: 2838.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int N = 100000;
struct node {
    int cnt;
    long long val;
} f[N + 5];

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

void add(int i, int n, long long d) {
    while (i <= n) {
        ++f[i].cnt, f[i].val += d;
        i += lowbit(i);
    }
    return;
}

int sum_n(int i) {
    int res = 0;
    while (i) {
        res += f[i].cnt;
        i -= lowbit(i);
    }
    return res;
}

long long sum_v(int i) {
    long long res = 0;
    while (i) {
        res += f[i].val;
        i -= lowbit(i);
    }
    return res;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        memset(f, 0, sizeof(f));
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            int a;
            scanf("%d", &a);
            add(a, n, (long long)a);
            int sum = i - sum_n(a) + 1;
            long long val = sum_v(n) - sum_v(a);
            ans += (long long)sum*(long long)a + val;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}
转载保留版权:http://haipz.com/blog/i/5750 - 海胖博客