AT_abc360_d [ABC360D] Ghost Ants

SakurajiamaMai · 2024-07-16 17:54:04 · 题解

题解中大部分都是二分和双指针，这里给出一个逆序对的题解，其实由于每个蚂蚁都有自己的方向且不会变，那么很明显的我们走完路程之后，如果原来标号小的蚂蚁走到了标号大的蚂蚁的后面那么两者一定相遇，所以可以使用逆序对。

但是有以下几点需要注意:

• 题目中蚂蚁的坐标不是升序的，不要被样例迷惑，一定要先排序
• 对于坐标相同的，我们按照标号从大到小排序，方便统计。

顺便给出一组样例

5
26
00011
-28 -55 48 -4 89

下面奉上代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct node{
    int x, id, s;
    bool operator<(const node &w) const{
        if(x == w.x) return id > w.id;
        else return x < w.x;
    }
}a[N];
int c[N], res;
bool cmp(node a, node b){
    return a.x < b.x;
}
void merge_sort(int l, int r){
    if(l == r) return;
    int mid = l + r >> 1, i = l, j = mid + 1, num = l;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    while(i <= mid && j <= r){
        if(a[i].id <= a[j].id) c[num++] = a[i++].id;
        else res += mid - i + 1, c[num++] = a[j++].id;
    }
    while(i <= mid) c[num++] = a[i++].id;
    while(j <= r) c[num++] = a[j++].id;
    for(int i = l; i <= r; i++) a[i].id = c[i];
}
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, t; cin >> n >> t;
    string s; cin >> s;
    s = " " + s;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        a[i] = {x, i, s[i] - '0'};  
    }
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1; i <= n; i++){
        a[i].id = i;
        if(a[i].s == 1) a[i].x += t;
        else a[i].x -= t;
    }
    sort(a + 1, a + 1 + n);
    merge_sort(1, n);
    cout << res << '\n';
    return 0;
}