Logo WF_wxl 的博客

博客

新博客

...
WF_wxl
2026-02-08 09:01:01
#include<bits/stdc++.h>
#define int long long
#define double long double
#define fi first
#define se second
#define pii pair<int,pair<int,int> >
#define endl '\n'
using namespace std;
const int N=2e5+10;
int n;
string s;
int a[N];
priority_queue<pii,vector<pii>,greater<pii> >pq;
map<pii,vector<pii>>vec;
map<pair<int,int>,bool>ban;
int cnt;
vector<pair<int,int>>ans;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    s=' '+s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        if(s[i]!=s[i+1]){
            pq.push({abs(a[i]-a[i+1]),{i,i+1}});
            int l=i,r=i+1;
            while(l-1>=1&&r+1<=n&&s[l-1]!=s[r+1]){
                l--,r++;
                vec[{abs(a[l+1]-a[r-1]),{l+1,r-1}}].push_back({abs(a[l]-a[r]),{l,r}});
            }
        }
    }
    while(pq.size()){
        pii tp=pq.top();
        pq.pop();
        if(ban[tp.se])continue ;
        cnt++;
        ans.push_back({tp.se.fi,tp.se.se});
        for(pii i:vec[tp]){
            pq.push(i);
        }
        int l=tp.se.fi;
        int r=tp.se.se;
        for(int i=1;i<=n;i++){
            ban[{i,l}]=1;
            ban[{i,r}]=1;
            ban[{l,i}]=1;
            ban[{r,i}]=1;
        }
    }
    cout<<cnt<<endl;
    for(auto i:ans){
        cout<<i.fi<<" "<<i.se<<endl;
    }
    return 0;
}
/*
8
GGGGBGBB
54 69 57 80 17 4 99 39
*/

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。