CF 45C Dancing Lessons(優先隊列)

維護一個優先隊列，按差值為關鍵字，如果差值一樣，按二元組排序。
然後維護一個類似鏈表的東西，記錄下一個元素以及上一個元素。
[cpp]  #include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <cstring>  
#include <cmath>  
#include <set>  
#include <vector>  
#include <queue>  
#define pb(a) push_back(a)  
#define mp(a,b) make_pair(a,b)  
using namespace std; 
const int N = 200005; 
struct Node{ 
    int l,r,d; 
    Node(){} 
    Node(int _l,int _r,int _d):l(_l),r(_r),d(_d){} 
    bool operator<(const Node n)const{ 
        return d!=n.d?d>n.d:l>n.l; 
    } 
}; 
priority_queue<Node>que; 
int n,a[N],flag[N]={0}; 
int next[N],pre[N]; 
char str[N]; 
vector<pair<int,int> >ans; 
int main(){ 
    scanf("%d%s",&n,str+1); 
    for(int i=1;i<=n;i++){ 
        scanf("%d",&a[i]); 
        pre[i]=i-1;next[i]=i+1; 
    } 
    for(int i=1;i<n;i++){ 
        if(str[i]!=str[i+1]) 
            que.push(Node(i,i+1,abs(a[i]-a[i+1]))); 
    } 
    while(!que.empty()){ 
        Node cur=que.top();que.pop(); 
        if(flag[cur.l]||flag[cur.r]) continue; 
        ans.pb(mp(cur.l,cur.r)); 
        int l=pre[cur.l],r=next[cur.r]; 
        flag[cur.l]=flag[cur.r]=1; 
        next[l]=r;pre[r]=l; 
        if(l<1||r>n) continue;  
        if(str[l]!=str[r]){ 
            que.push(Node(l,r,abs(a[l]-a[r]))); 
        } 
    } 
    printf("%d\n",ans.size()); 
    for(int i=0;i<ans.size();i++) 
        printf("%d %d\n",ans[i].first,ans[i].second); 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
using namespace std;
const int N = 200005;
struct Node{
    int l,r,d;
    Node(){}
    Node(int _l,int _r,int _d):l(_l),r(_r),d(_d){}
    bool operator<(const Node n)const{
        return d!=n.d?d>n.d:l>n.l;
    }
};
priority_queue<Node>que;
int n,a[N],flag[N]={0};
int next[N],pre[N];
char str[N];
vector<pair<int,int> >ans;
int main(){
    scanf("%d%s",&n,str+1);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        pre[i]=i-1;next[i]=i+1;
    }
    for(int i=1;i<n;i++){
        if(str[i]!=str[i+1])
            que.push(Node(i,i+1,abs(a[i]-a[i+1])));
    }
    while(!que.empty()){
        Node cur=que.top();que.pop();
        if(flag[cur.l]||flag[cur.r]) continue;
        ans.pb(mp(cur.l,cur.r));
        int l=pre[cur.l],r=next[cur.r];
        flag[cur.l]=flag[cur.r]=1;
        next[l]=r;pre[r]=l;
        if(l<1||r>n) continue;
        if(str[l]!=str[r]){
            que.push(Node(l,r,abs(a[l]-a[r])));
        }
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)
        printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}