问题：小和或者逆序数问题
求数组中，左数小于右数的和。
输入[1 2 3 4 5]
输出20
2的位置 res += 1 res=1
3的位置 res += 1 + 2 res = 4
4的位置res += 1 + 2 + 3 res = 10
5的位置res += 1 + 2 + 3 + 4 res = 20
归并代码
#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; void g(vector<int> &v, int size) { int n = rand() % size + 1; for (int i = 0; i < n; i++) { v.push_back(rand() % 100000007); } } int rightfunc(vector<int> a) { int res = 0; for (int i = 0; i < a.size(); i++) { for (int j = 0; j < i; j++) { if (a[i] > a[j]) { res += a[j]; } } } return res; } int Merge(vector<int> &a, int l1, int r1, int l2, int r2) { vector<int> b; int res = 0; int pos1 = l1, pos2 = l2; while (pos1 <= r1 && pos2 <= r2) { if (a[pos1] < a[pos2]) { res += a[pos1] * (r2 - pos2 + 1); b.push_back(a[pos1++]); } else if (a[pos1] > a[pos2]) { b.push_back(a[pos2++]); } else { b.push_back(a[pos1]); ++pos1; ++pos2; } } while (pos1 <= r1) { b.push_back(a[pos1++]); } while (pos2 <= r2) { b.push_back(a[pos2++]); } for (int i = 0; i < b.size(); i++) { a[i + l1] = b[i]; } return res; } int f(vector<int>& a, int k, int n) { int res = 0; if (n > 1) { int mid = n / 2; res += f(a, k, mid); res += f(a, k + mid, n - mid); res += Merge(a, k, k + mid - 1, k + mid, k + n - 1); } return res; } void test() { int N = 50; while(N--) { vector<int> a, b; g(a, 1000); int res1 = rightfunc(a); int res2 = f(a, 0, (int)a.size()); if (res1 == res2) { cout << N << endl; } else { cout << "error" << endl; } } cout << "OK" << endl; } int main() { //test(); vector<int> a; int N, x; cin >> N; for (int i = 0; i < N; i++) { cin >> x; a.push_back(x); } int res = f(a, 0, (int)a.size()); cout << res << endl; return 0; }
