逆序对WA
查看原帖
逆序对WA
766582
System32楼主2024/7/2 20:39

#include <bits/stdc++.h>
using namespace std;

long long ans;

struct node {
    long long a, b;
    bool operator<=(const node &k) const { return this->b <= k.b; }
} a[200010], temp[200010];

bool cmp(node a, node b) { return a.a < b.a; }

void merge_pai(int l, int r, int mid) {
    int i = l, p = l, j = mid;
    while (i < mid && j <= r) {
        if (a[i] <= a[j])
            temp[p++] = a[i++];
        else {
            temp[p++] = a[j++];
            ans += mid - i;
        }
    }
    while (i < mid)
        temp[p++] = a[i++];
    while (j <= r)
        temp[p++] = a[j++];
    p = i = l;
    while (p <= r)
        a[i++] = temp[p++];
}
void merge_sort(int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        merge_pai(l, r, mid + 1);
    }
}

int main() {
    long long n, t;
    string s;
    cin >> n >> t >> s;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a;
    }
    stable_sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        a[i].b = i;
        if (s[i - 1] == '0') {
            a[i].a -= t;
        } else {
            a[i].a += t + 1;
        }
    }
    stable_sort(a + 1, a + n + 1, cmp);
    merge_sort(1, n);
    cout << ans << endl;
    return 0;
}

样例通过了。

2024/7/2 20:39
加载中...