Codeforces 45 C. Dancing Lessons

問題

男女n人が一列に並んでいる。
それぞれの性別およびスキルの値が与えられる。

この列に対して、以下のような方法でペアを作れるだけ作る。

• 列で隣り合う男女のうち、スキルの差の絶対値が最も小さいペア（複数ある場合最も左のペア）を選び、ペアを作る。二人は列から外す。

このとき、出来るペアを順に出力せよ。

制約条件

n≦2*10^5

方針

両隣の人を覚えておく。
ペアが作られるたびにその部分だけ関係を更新する。

隣合うペアのうちのスキルの差が最小のものを選ぶため、
差をpriority_queueに入れられれば良いのであるが、
ペアを一組（たとえばa,bを）選ぶと、priority_queueからaまたはbを片方として含むペアを取り除く操作が必要であるため、
stlのpriority_queueをそのまま使うことは出来ない。

priority_queueの代わりにsetを使えば、要素の削除および最小値の取り出しがO(log n)時間で出来る。

ソースコード

int n,s[200001];
char g[200001];
set<pair<int,pi> > S;
vector<pi> ans;
int l[200001],r[200001];

void run(){
  cin>>n>>g;
  rep(i,n){
    cin>>s[i];
    l[i]=r[i]=-1;
  }
  S.clear();
  ans.clear();
  rep(i,n-1){
    if(g[i]!=g[i+1])S.insert(mp(abs(s[i]-s[i+1]),mp(i,i+1)));
    r[i]=i+1;
    l[i+1]=i;
  }
  while(!S.empty()){
    int a=(*S.begin()).second.first, b=(*S.begin()).second.second;
    int aa=l[a], bb=r[b];
    S.erase(S.begin());
    ans.push_back(mp(a+1,b+1));
    if(aa>=0){
      S.erase(mp(abs(s[a]-s[aa]),mp(aa,a)));
      r[aa]=bb;
    }
    if(bb>=0){
      S.erase(mp(abs(s[b]-s[bb]),mp(b,bb)));
      l[bb]=aa;
    }
    if(aa>=0&&bb>=0&&g[aa]!=g[bb])S.insert(mp(abs(s[aa]-s[bb]),mp(aa,bb)));
  }
  cout<<ans.size()<<endl;
  rep(i,ans.size())cout<<ans[i].first<<" "<<ans[i].second<<endl;
}