P1878 舞蹈课
小根堆
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define maxn 200005 4 #define inf 1<<30 5 using namespace std; 6 struct data{ 7 int w,pos; 8 }; 9 bool operator > (data a,data b){ return a.w>b.w||(a.w==b.w&&a.pos>b.pos); } 10 int n,ans; 11 int a[maxn],nxt[maxn],pre[maxn],a1[maxn],a2[maxn]; 12 char ch[maxn]; 13 bool if_[maxn]; 14 priority_queue<data,vector<data>,greater<data> >q; 15 inline int read() 16 { 17 int x=0,f=1;char ch=getchar(); 18 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 19 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 23 int main() 24 { 25 n=read(); if_[0]=1; 26 scanf("%s",ch+1); 27 for(int i=1;i<=n;i++) a[i]=read(); 28 for(int i=1;i<n;i++) nxt[i]=i+1; 29 for(int i=2;i<=n;i++) pre[i]=i-1; 30 for(int i=1;i<n;i++) 31 if(ch[i]!=ch[i+1]) 32 q.push((data){abs(a[i]-a[i+1]),i}); 33 while(!q.empty()) 34 { 35 int mn=q.top().w,now=q.top().pos; q.pop(); 36 int l=pre[now],t=nxt[now],r=nxt[t]; 37 if(if_[now]||if_[t]) continue; 38 if(abs(a[now]-a[t])!=mn||ch[now]==ch[t]) continue; 39 if_[now]=if_[t]=1; 40 a1[++ans]=now; a2[ans]=t; 41 if(l&&r&&ch[r]!=ch[l]) q.push((data){abs(a[r]-a[l]),l}); 42 nxt[l]=r; pre[r]=l; 43 } 44 printf("%d ",ans); 45 for(int i=1;i<=ans;i++) 46 printf("%d %d ",a1[i],a2[i]); 47 return 0; 48 }