好啦!闲聊到此为止,开始分享代码。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
const int maxn = 5e5 + 5;
int a[maxn], b[maxn];
long long ans = 0;
void rop(int l, int r) {
int mid = (l + r) >> 1;
if (l == r) {
return;
} else {
rop(l, mid);
rop(mid + 1, r);
}
int i = l;
int j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] > a[j]) {
ans += mid - i + 1;
b[k++] = a[j];
++j;
} else {
b[k++] = a[i];
++i;
}
}
while (i <= mid) {
b[k++] = a[i];
++i;
}
while (j <= r) {
b[k++] = a[j];
++j;
}
for (int t = l; t <= r; ++t) {
a[t] = b[t];
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
rop(1, n);
cout << ans;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
long long c[maxn], n;
struct node {
int idx, w;
}v[maxn];
int lowbit (int a) {
return (-a) & a;
}
long long cnt (int a) {
long long ans = 0;
for(; a > 0; a -= lowbit(a)) {
ans += c[a];
}
return ans;
}
void add (int a, long long b){
for (; a <= n; a += lowbit(a)) {
c[a] += b;
}
}
bool cmp(node x, node y) {
return x.w >= y.w;
}
void best_coder() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
v[i].idx = i;
scanf("%d", &v[i].w);
}
stable_sort(v + 1, v + 1 + n, cmp);
long long ans = 0;
for (int i = 1; i <= n; ++i) {
add(v[i].idx, 1);
ans += cnt(v[i].idx - 1);
}
printf("%lld", ans);
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
末尾给大家分享下小码匠在这道题的囧事:
这种情况对于学信竞孩子来说是很常见的,即使大佬级别的人,有时候做ABC的C题也要提交好几次才能AC。
作为家长不要轻易怀疑自己的孩子,孩子的自信来源于自己也同样来源于家庭。
要在后面多观察,找到助力孩子学习的手段或者方法。
而且也不要整天泡在各种信奥微信群中,拿自家娃和其他家娃对比,情绪化的家长往往起不到好作用,反作用肯定会有的。
好啦,今天就分享到这里。