hong123 @ 2019-08-13 16:25:14
#include<iostream>
#include<cstdio>
using namespace std;
int a[500005] , temp[500005] , n;
long long ans = 0;
void Merge(int left, int mid, int right)
{
int i = left, j = mid + 1, k = 0;
while ((i <= mid) && (j <= right))
{
if (a[i] < a[j])temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
ans += mid - i + 1;
}
}
while (i <= mid)
{
temp[k++] = a[i++];
}
while (j <= right)temp[k++] = a[j++];
}
void MergeSort(int left, int right)
{
int mid, i, k;
if (left < right)
{
mid = (left + right) / 2;
MergeSort(left, mid);
MergeSort(mid + 1, right);
Merge(left, mid, right);k = 0;
for (i = left;i <= right;i++)a[i] = temp[k++];
}
}
inline int read() {//快读
char ch = getchar();
int x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-') f = -1;ch = getchar(); }
while (ch >= '0'&&ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
return x * f;
}
int main()
{
int i;
cin >> n;
for (i = 0;i < n;i++) a[i] = read();;
MergeSort(0, n - 1);
cout << ans << endl;
system("pause");
return 0;
}
by hong123 @ 2019-08-13 16:26:06
都是wrong answer
by 静之城 @ 2019-08-22 08:37:38
超了吧
by 静之城 @ 2019-08-22 08:38:06
@hong123
by hong123 @ 2019-08-26 15:25:32
@静之城 应该不是超时,是答案不对