P1878 舞蹈课题解

Kalium · 2021-04-03 16:14:52 · 题解

P1878 舞蹈课题解

本题解有开防抄袭（freopen），文件名是歌名，有兴趣的听听

题意：

一群人跳舞，必须和相邻的异性跳舞，然后在每对的舞技差的绝对值最小时，输出配对个数和配对顺序

思路：

前置芝士：堆

我们建一个堆，每个相邻的异性的差的绝对值和这两个的位置插入。

插入后，我们看看如何配对以及在取出后如何再次插入

其实很容易

我们可以用 flag_i 数组表示 i 这个人有没有跳过了

然后以取出的两个人为中心，分别往左右移，碰到异性再次插入

当然，每次取出存答案是必然的，这就不用我说的吧

细节：

在堆中比较是否交换时，一定要考虑舞技差的绝对值相同时，选取左边编号较小的

本菜鸡因为这个被卡了 5 个月（但是我中间咕了4个多月）

代码：

#include <cstdio>
#include <cmath>
#include <iostream>
#define ri register int

using namespace std;

const int N = 2e5 + 7;

struct Heap {
    int x, id1, id2;
} heap[N];

int sz;

int n;

char c;

int a[N], b[N];

int ans;

int l[N], r[N];

int flag[N];

inline void push(int x, int idx1, int idx2) {//小根堆 
    int now = (++ sz);

    heap[now].x = x;
    heap[now].id1 = idx1;
    heap[now].id2 = idx2;

    while (now > 1) {
        int fa = (now >> 1);

        if (heap[fa].x > heap[now].x)
            swap(heap[fa], heap[now]);//技术差小的先 
        else if (heap[now].x == heap[fa].x && heap[now].id1 < heap[fa].id1)
            swap(heap[fa], heap[now]);//技术差相同，左的先来 
        else
            break;

        now = fa;
    }

    return ;
}//插入 

inline void pop() {
    swap(heap[1], heap[sz]);
    sz --;

    int now = 1;

    while ((now << 1) <= sz) {
        int son = (now << 1);

        if (son + 1 <= sz && heap[son].x > heap[son + 1].x)
            son ++;
        else if (heap[son].x == heap[son + 1].x && heap[son].id1 > heap[son + 1].id1)
            son ++;

        if (heap[son].x < heap[now].x)
            swap(heap[son], heap[now]);
        else if (heap[son].x == heap[now].x && heap[son].id1 < heap[now].id1)
            swap(heap[son], heap[now]);
        else
            break;

        now = son;
    }

    return ;
}//取出 

int main() {
    freopen("something just like this.in", "r", stdin);
    freopen("something just like this.in", "w", stdout);

    scanf("%d", &n);

    for (ri i = 1; i <= n; i ++) {
        cin >> c;

        if (c == 'B') b[i] = 1;
    }

    for (ri i = 1; i <= n; i ++)
        scanf("%d", &a[i]);

    for (ri i = 2; i <= n; i ++) {
        if (b[i - 1] ^ b[i])
            push(abs(a[i] - a[i - 1]), i - 1, i);
    }

    /*for (int i = 1; i <= sz; i ++)
        cout << id1[i] << " " << id2[i] << endl;*/
//  cout << sz << endl;

    while (sz) {
        int x1 = heap[1].id1;
        int x2 = heap[1].id2;

        pop();

        if (! flag[x1] && ! flag[x2]) {
            l[++ ans] = x1;
            r[ans] = x2;
            flag[x1] = flag[x2] = 1;

            while (x1 > 0 && flag[x1]) x1 --;
            while (x2 <= n && flag[x2]) x2 ++;

            if (x2 <= n && x1 > 0 && b[x1] ^ b[x2])
                push(abs(a[x1] - a[x2]), x1, x2);
        }
    }

    printf("%d\n", ans);

    for (ri i = 1; i <= ans; i ++)
        printf("%d %d\n", l[i], r[i]);

    fclose(stdin);
    fclose(stdout); 

    return 0;
}