题解 P1878 【舞蹈课】

巧若拙 · 2017-03-02 10:38:36 · 题解

算法思路：

设置一个Node类存储每对舞伴的左右舞者下标l，r和舞技差值w。

一开始读取所有相邻的舞伴信息，并插入到最小堆。

然后执行以下循环体，直至最小堆为空：

记录堆顶元素的舞者下标（当前配对舞者），标注当前舞者已配对，并删除堆顶元素，

然后删除所有涉及已配对舞者的堆顶元素，确保下次提取的顶点是满足条件的配对。

接下来跳过所有已配对舞者，用其两侧的舞者填补空白，查看是否能形成新的配对，

若能配对，则生成新结点，并插入到最小堆。

注意：题目要求“如果不止一对，那么最左边的那一对出列”，所以建立最小堆的时候，

不仅仅要看w值，还要比较左侧舞者的编号，编号小的靠前。

所以重载>运算符的时候要同时比较w和l的值。

#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;

class Node { public:

// void PrintNode() {cout << l+1 << " " << r+1 << " --" << w << endl;}

void SetNode(int p1, int p2, int v) {l = p1; r = p2; w = v;}

        int GetL() {return l;}
        int GetR() {return r;}
        int GetW() {return w;}
        friend bool operator > (const Node &op1, const Node &op2) 
        {
            return op1.w > op2.w || (op1.w == op2.w && op1.l > op2.l);
        }

private:

       int l, r;  //分别表示左右两个舞伴的下标 
       int w; 
};
int main()
{
    priority_queue<Node, vector<Node>, greater<Node> > H;
    Node t;
    const int size = 200000;
    char S[size];
    int A[size];
    int n;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        cin >> S[i];
    }
    for (int i=0; i<n; i++)
    {
        cin >> A[i];
    }
    for (int i=1; i<n; i++)//不同性别的都入队
    {
        if (S[i] != S[i-1])
        {
            t.SetNode(i-1, i, abs(A[i]-A[i-1])); 
            H.push(t);
        }
    }    
    bool F[size] = {0}; //标注是否已经配对成功 
    int P[size/2][2]; //存储配对成功的舞者编号 
    int s = 0;
    int l, r, p1, p2; //分别存储左右舞伴的下标
    while (!H.empty())
    {
        t = H.top();
        l = t.GetL();
        r = t.GetR(); 
        F[l] = F[r] = true; //标注该对舞伴已配对
        P[s][0] = l + 1; //记录配对舞伴编号（下标+1） 
        P[s++][1] = r + 1;
        do //除去重复配对的顶点，确保下次提取的顶点是满足条件的配对 
        {
             H.pop();
            if (H.empty())    
               break;
            t = H.top();
            p1 = t.GetL();
            p2 = t.GetR(); 
        } while(F[p1] || F[p2]);
        //跳过已经配对的舞者
        while(l >= 0 && F[l])
        {
            l--;
        }
        while(r < n && F[r])
        {
            r++;
        }
        if (l>=0 && r<n && S[l] != S[r])//有缘千里来相会
        {
            t.SetNode(l, r, abs(A[l]-A[r])); 
            H.push(t);
        }
    }
    cout << s << endl;
    for (int i=0; i<s; i++)
    {
         cout << P[i][0] << " " << P[i][1] << endl;
    }
 //   system("pause");    
    return 0;
}