直接自定义小根堆0分,太玄学了,求调
查看原帖
直接自定义小根堆0分,太玄学了,求调
1169915
miku010123楼主2024/8/23 12:12
#include<bits/stdc++.h>
using namespace std;
#define int long long 

struct node
{
    int l;
    int r;
    int num;
    bool operator<(const node&t)const 
    {
        if(this->num!=t.num)
            return this->num>t.num;
        return this->l>t.l;
    }
    /* data */
};

void solve()
{
    int n;
    string s;
    cin>>n>>s;
    vector<int>a(n);
    vector<node>ans;
    vector<bool>st(n,0);
    priority_queue<node>q;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++)
    {
        if(s[i]!=s[i+1])
        {
            q.push((node){i,i+1,abs(a[i]-a[i+1])});
        }
    }
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int l=t.l,r=t.r;
        if(st[l]==1||st[r]==1)
            continue;
        ans.push_back((node){l,r,0});
        st[l]=st[r]=1;
        if(l-1>=0&&r+1<n&&s[l-1]!=s[r+1]&&!st[l-1]&&!st[r+1])
        {
            q.push((node){l-1,r+1,abs(a[l-1]-a[r+1])});
        }
    }
    int len=ans.size();
    cout<<len<<'\n';
    for(int i=0;i<len;i++)
    {
        cout<<ans[i].l+1<<' '<<ans[i].r+1<<'\n';
    }
}

signed main()
{
    solve();
    return 0;
}

2024/8/23 12:12
加载中...