CF45C

nxd_oxm · 2023-09-25 22:47:17 · 题解

题意

我们的题目说啊，有一群男生女生站成一排，相邻的异性可以组成一组，每次捏就选取舞蹈技能差值最小的一组，把他们两个挑出来，如果有一样的就选取最左边的。（重点！）

思路

首先我们要非常方便的找的左右，并且还要方便的删除，那肯定是用链表。

我们要找出差值最小的一组，还得找 n 次，那最好用优先队列，找出差值最小的一对。

先定义一个结构体，把它作为优先队列的载体。每个值存他们的差值 to，左边人的编号 left，右边人的编号 right。

只要每次取出优先队列的队首，将他们存起来，再检测新位置补上后会不会出现一男一女在一起，如果有就入队。

注意要拿个数组存一下当前的左右两人出队没，出对了就不能再算了。

一定要注意，差值相同的要拿最左边的，写结构体排序的函数的时候就得注意加上。

（我就被坑了半个小时）

不会超时，时间复杂度应该是 n \log n。

AC code

#include<bits/stdc++.h>
#include<queue>
#define int long long
#define f(i,j,n) for(int i=j;i<=n;i++)
using namespace std;
struct anv{
    int to;
    char gen;
    int left;
    int right;
}a[200001];
struct av{
    int to;
    int left;
    int right;
    av(int t,int l,int r):to(t),left(l),right(r){
    }
    friend bool operator > (struct av a,struct av b){
        return a.to==b.to?a.left>b.left:a.to>b.to;
    }
};
int p[200001][2]={},pi;
bool vis[200001];
priority_queue<av,vector<av>,greater<av> >q;
signed main(){
    int n;
    cin>>n;
    a[0].right=1;
    f(i,1,n){
        a[i].left=i-1;
        a[i].right=i+1;
    }
    f(i,1,n){
        cin>>a[i].gen;
    }
    f(i,1,n){
        cin>>a[i].to;
        if(i>1&&a[i-1].gen!=a[i].gen){
            q.push(av(abs(a[i-1].to-a[i].to),i-1,i));
        }
    }
    while(q.empty()==0){
        av t=q.top();
        q.pop();
        if(vis[t.left]||vis[t.right]){
            continue;
        }
        pi++;
        p[pi][0]=t.left;
        p[pi][1]=t.right;
        int l=t.left,r=t.right;
        vis[l]=vis[r]=1;
        a[a[l].left].right=a[r].right;
        a[a[r].right].left=a[l].left;
        if(a[l].left>=1&&a[r].right>=1&&a[r].right<=n&&a[a[l].left].gen!=a[a[r].right].gen){
            q.push(av(abs(a[a[l].left].to-a[a[r].right].to),a[l].left,a[r].right));
        }
    }
    cout<<pi<<endl;
    f(i,1,pi){
        cout<<p[i][0]<<" "<<p[i][1]<<endl;
    }
    return 0;
}

这里用了一下循环的简便写法，就定义了一个宏。

看 4 行。