求条
  • 板块P1878 舞蹈课
  • 楼主Gyf117
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/17 17:13
  • 上次更新2024/12/17 21:03:58
查看原帖
求条
947527
Gyf117楼主2024/12/17 17:13

rt。

// Problem: P1878 舞蹈课
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1878
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n;
int b[N];
int a[N],l[N],r[N];
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
int vis[N];
int k;
vector<pair<int,int>> ans;
int main(){
  cin>>n;
  for(int i=1;i<=n;++i){
    char ch;
    cin>>ch;
    b[i]=ch=='B';
  }
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  for(int i=1;i<n;++i){
    if(b[i]^b[i+1]){
      q.emplace(abs(a[i]-a[i+1]),make_pair(i,i+1));
    }
  }
  while(q.size()){
    pair<int,pair<int,int>> t=q.top();
    q.pop();
    if(vis[t.second.first]||vis[t.second.second]){
      continue;
    }
    vis[t.second.first]=1;
    vis[t.second.second]=1;
    r[l[t.second.first]]=r[t.second.second];
    l[r[t.second.second]]=l[t.second.first];
    if(b[l[t.second.first]]^b[r[t.second.second]]){
      q.emplace(abs(a[l[t.second.first]]-a[r[t.second.second]]),make_pair(l[t.second.first],r[t.second.second]));
    }
    ++k;
    ans.emplace_back(t.second);
  }
  cout<<k<<endl;
  for(pair<int,int> i:ans){
    cout<<i.first<<' '<<i.second<<endl;
  }
  return 0;
}
2024/12/17 17:13
加载中...