结论1:对于一个序列每次只能交换相邻两个元素的位置则将其变为有序序列的最少操作次数等于原序列中逆序对的数量
结论2:每个数交换次数 = 前面比该数大的数 + 后面比该数小的数 时 不高兴程度之和最小 且此时 每个数的交换次数之和 = 2 * 逆序对数量
求逆序对数量 -> 归并排序 175ms
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long ll;
const int N = 100010;
int n;
PII a[N], b[N];
int cnt[N]; // 存放每个元素交换次数
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (a[i].x <= a[j].x) {
cnt[a[i].y] += (j - 1) - (mid + 1) + 1; // a[mid + 1 ~ j - 1].x 一定小于 a[i].x 对于a[i].y 加上后面比它小的数的个数
b[k++] = a[i++];
} else {
cnt[a[j].y] += mid - i + 1; // a[i ~ mid].x 一定大于 a[j].x 对于a[j].y 加上前面比它大的数的个数
b[k++] = a[j++];
}
while (i <= mid) cnt[a[i].y] += (j - 1) - (mid + 1) + 1, b[k++] = a[i++];
while (j <= r) b[k++] = a[j++];
for (int i = l, k = 0; i <= r; i++, k++) a[i] = b[k];
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i].x), a[i].y = i;
merge_sort(0, n - 1);
ll res = 0;
for (int i = 0; i < n; i++) res += (ll)(1 + cnt[i]) * cnt[i] / 2;
printf("%lld", res);
return 0;
}
统计一个数前面有多少个数比它小和后面有多少个数比它大 -> 树状数组 185ms
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010, M = 1000010;
int n;
int a[N];
int cnt[N];
int tr[M];
int lowbit(int x) {
return x & -x;
}
void add(int x, int k) {
for (int i = x; i <= M - 1; i += lowbit(i)) tr[i] += k;
}
int ask(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]), a[i]++; // 树状数组索引从 1 开始
// 统计每个数前面有多少个数比它大
for (int i = 0; i < n; i++) {
cnt[i] += ask(M - 1) - ask(a[i]); // 遍历到 i 时 a[i] + 1 ~ M - 1 的数出现的次数
add(a[i], 1);
}
memset(tr, 0, sizeof(tr)); // 清空树状数组
// 统计每个数后面有多少个数比它小
for (int i = n - 1; i >= 0; i--) {
cnt[i] += ask(a[i] - 1); // 遍历到 i 时 1 ~ a[i] - 1 的数出现的次数
add(a[i], 1);
}
ll res = 0;
for (int i = 0; i < n; i++) res += (ll)(1 + cnt[i]) * cnt[i] / 2;
printf("%lld", res);
return 0;
}