题解 P1878 【舞蹈课】

· · 题解

作为一个标签党，点开标签发现是二叉堆

众所周知，嗯，没错，就是二叉堆

算法流程


1.先定义一个结构体堆 + 重载运算符

2.把男女的性别在f数组里表示好

3.把相邻的舞者入队（不能同性别）

4.找到符合条件（舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，
那么最左边的那一对出列）的舞者出队，并定义为“跳过了”

5.再找一对从上一对跳舞的人继续找相邻的舞者入队（得一男一女）

6.输出 + AC

先讲一下代码里有的一些并不是很难的东西吧~

1.priority_queue

称为堆，也叫优先队列，是一种二叉树

至于小根堆和大根堆么~（就不说了，搜百度去吧）简单的提一下吧（怕被差评）

大根堆：堆顶元素最大，像一颗二叉树一样，越往下越小

小根堆：堆顶元素最小，像一颗二叉树一样，越往下越大

堆的那些简单操作就上网百度去吧

定义个堆默认是大根堆，所以重载运算符（定义结构体的排序方式）的时候要注意（最重要，敲黑板）把运算符反过来

2.pair

是一种常用的数据结构

简单的提一下吧

pair顾名思义，是一对的意思，在数据结构中也如此

定义：

pair < 第一个的变量类型, 第二个的变量类型 > 变量或数组名称

先用做int int ans[10001]吧

第一个元素：

ans[i].first

第二个元素：

ans[i].second

先讲这么多吧（额，这才几个字），够了

好了，看代码（终于到代码了，累死了）

code ：

//代码里的register均可省去，是用于优化的 
#include <bits/stdc++.h>
using namespace std;
pair < int, int > ans[1000001];//定义pair来存答案 
int n, q[1000001], z;//z是答案总数 
string s;
bool vis[1000001], f[1000001];//vis是用来判断是否选过这个人，f数组表示是男是女(男是true，女是false) 
/*
struct node
{
    int x, y, z;
    friend bool operator < (node a, node b)
    {
        if(a.z == b.z)
        {
            return a.x < b.x;
        }
        else
        {
            return a.z < b.z;
        }
    }
};
*/
struct node
{
    int x, y, z;//x为其中一个舞者的编号，y为另一个，z为舞技之差
    friend bool operator < (node a, node b)
    {
        if(a.z == b.z)
        {
            return a.x > b.x;//priority_queue默认大根堆，要反过来写 
        }
        else
        {
            return a.z > b.z;//同理 
        }
    }
};//不用定义结构体数组 
priority_queue < node, vector < node > > pru;//加不加vector都一样，加能更快一些 
int main()
{
    scanf("%d", &n);
    cin >> s;
    for(register int i = 0; i < n; ++i)
    {
        if(s[i] == 'B')//用f数组表示男女 
        {
            f[i + 1] = true;//要加一(string是从0 ~ n - 1的) 
        }
        else//不是男就是女
        {
            f[i + 1] = false;
        }
    }
    for(register int i = 1; i <= n; ++i)
    {
        scanf("%d", &q[i]);
    }
    for(register int i = 1; i < n; ++i)
    {
        if(f[i] != f[i + 1])//不能男和男跳舞，女和女跳舞 
        {
            pru.push((node){i, i + 1, abs(q[i] - q[i + 1])/*要加abs*/});//可以把它们强制转化到一个结构体里 
        }
    }
    while(!pru.empty())
    {
        int x = pru.top().x;//取出第一个人来 
        int y = pru.top().y;//取出第二个人来 
        pru.pop();//pop掉 
        if(!vis[x] && !vis[y])//不能有一个人跳过舞了 
        {
            vis[x] = true;//改成跳过了 
            vis[y] = true;
            ans[++z].first = x;//存答案 
            ans[z].second = y;//z只加一遍 
            //再找一对儿相邻的入队
            //x向左边，y向右边(因为x小，y大) 
            while(x > 0 && vis[x])//跳过了或小于零都不行 
            {
                --x;//往左边 
            }
            while(y <= n && vis[y])//跳过了或大于n都不行 
            {
                ++y;//往右边 
            }
            if(x > 0 && y <= n/*有点多余*/ && f[x] != f[y])//不能男和男或女和女啊 
            {
                pru.push((node){x, y, abs(q[x] - q[y])});//强制转化成结构体再入队 
            }
        }
    }
    printf("%d\n", z);//先输出总数 
    for(register int i = 1; i <= z; ++i)
    {
        printf("%d %d\n", ans[i].first, ans[i].second);//输出舞者 
    }
    return 0;
}

求过 + 求赞