舞蹈课 (dancingLessons)
堆的操作
注意此处用greater - 大根堆
#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<cstdlib>#include<iostream>#include<functional>#include<algorithm>using namespace std;#define MAXN (200000 + 10)#define MAXAI (10000000 + 10)int n;char s[MAXN];int a[MAXN];bool b[MAXN];struct pair2{int x,y,w;}ans[MAXN];bool operator>(const pair2 a,const pair2 b){if (a.w==b.w) return a.x>b.x;return a.w>b.w;}void cout_pair(const pair2 a){printf("%d %d\n",a.x,a.y);}priority_queue <pair2, vector<pair2>, greater<pair2> > q;void push(int x,int y){pair2 now;now.x=x;now.y=y;now.w=abs(a[x]-a[y]);q.push(now);//cout<<"add "<<now.x<<' '<<now.y<<' '<<now.w<<'\n';}int main(){freopen("dancingLessons.in","r",stdin);freopen("dancingLessons.out","w",stdout);scanf("%d\n%s",&n,s);for (int i=1;i<=n;i++) scanf("%d",&a[i]);memset(b,0,sizeof(b));for (int i=1;i<n;i++)if (s[i-1]!=s[i]) push(i,i+1);int tot=0;while (!q.empty()){pair2 now=q.top();//cout_pair(now);q.pop();if (b[now.x]||b[now.y]) continue;b[now.x]=1;b[now.y]=1;ans[++tot]=now;int l=now.x-1,r=now.y+1;if (l<1||r>n) continue;while (l>1&&b[l]) l--;while (r<n&&b[r]) r++;if (b[l]||b[r]) continue;if (s[l-1]!=s[r-1]) push(l,r);}printf("%d\n",tot);for (int i=1;i<=tot;i++) cout_pair(ans[i]);//while (1);return 0;}