51Nod-3234 小明爱配对 题解

小明爱配对

题目大意

给定一个序列，给序列中的人两两配对

1. 相邻男女可以配对
2. 优先选择权值相差最小的一对，不止一对选择下标最小的一对
3. 配对成功后从原序列中删除，原来不相邻的可以变成相邻
4. 一直到无法配对为止

按配对的先后顺序求所有的对

解题思路

使用堆去存储配对信息

对初始序列扫描一遍，把所有符合要求的对放入堆中

每次从堆中取出一个配对，并在原序列中删除，并把新的相邻可配对元素放入堆中

删除的复杂度较高，可以使用链表解决

也可以使用标记的方式，同时对每个元素分别记录左右位置信息，当删除配对时更新左右位置信息，将元素标记为删除，可以防止某个元素被重复使用

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m;
vector<pair<int, int> > ans;
vector<pair<int, int> > a;
bool vis[N];
int l[N], r[N];

struct Node {
    int l, r, sub;
    Node(int l = 0, int r = 0, int sub = 0) : l(l), r(r), sub(sub) { }
};

struct cmp {
    bool operator () (Node a, Node b){
        if (a.sub == b.sub) {
            if (a.l == b.l) {
                return a.r > b.r;
            }
            return a.l > b.l;
        }
        return a.sub > b.sub;
    }
};

int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;   int x;
        cin >> s >> x;
        a.emplace_back(make_pair(s == "B", x));
        l[i] = i - 1;   r[i] = i + 1;
    }
    r[n - 1] = -1;
    priority_queue<Node, vector<Node>, cmp> pq;
    for (int i = 1; i< n; i++) {
        if (a[i - 1].first ^ a[i].first) {
            pq.push(Node(i - 1, i, abs(a[i - 1].second - a[i].second)));
        }
    }
    while (pq.size()) {
        auto x = pq.top();  pq.pop();
        if (vis[x.l] || vis[x.r]) continue;
        ans.emplace_back(make_pair(x.l, x.r));
        vis[x.l] = vis[x.r] = true;
        int ll = l[x.l], rr = r[x.r];
        if (~ll && ~rr) {
            r[ll] = rr;
            l[rr] = ll;
            if (a[ll].first ^ a[rr].first) {
                pq.push(Node(ll, rr, abs(a[ll].second - a[rr].second)));
            }
        }
    }
    cout << ans.size() << "\n";
    for (auto x : ans) {
        cout << x.first + 1 << " " << x.second + 1 << "\n";
    }
    return 0;
}