CF 45C Dancing Lessons(优先队列)
维护一个优先队列,按差值为关键字,如果差值一样,按二元组排序。
然后维护一个类似链表的东西,记录下一个元素以及上一个元素。
[cpp] #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
using namespace std;
const int N = 200005;
struct Node{
int l,r,d;
Node(){}
Node(int _l,int _r,int _d):l(_l),r(_r),d(_d){}
bool operator<(const Node n)const{
return d!=n.d?d>n.d:l>n.l;
}
};
priority_queue<Node>que;
int n,a[N],flag[N]={0};
int next[N],pre[N];
char str[N];
vector<pair<int,int> >ans;
int main(){
scanf("%d%s",&n,str+1);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
pre[i]=i-1;next[i]=i+1;
}
for(int i=1;i<n;i++){
if(str[i]!=str[i+1])
que.push(Node(i,i+1,abs(a[i]-a[i+1])));
}
while(!que.empty()){
Node cur=que.top();que.pop();
if(flag[cur.l]||flag[cur.r]) continue;
ans.pb(mp(cur.l,cur.r));
int l=pre[cur.l],r=next[cur.r];
flag[cur.l]=flag[cur.r]=1;
next[l]=r;pre[r]=l;
if(l<1||r>n) continue;
if(str[l]!=str[r]){
que.push(Node(l,r,abs(a[l]-a[r])));
}
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)
printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
using namespace std;
const int N = 200005;
struct Node{
int l,r,d;
Node(){}
Node(int _l,int _r,int _d):l(_l),r(_r),d(_d){}
bool operator<(const Node n)const{
return d!=n.d?d>n.d:l>n.l;
}
};
priority_queue<Node>que;
int n,a[N],flag[N]={0};
int next[N],pre[N];
char str[N];
vector<pair<int,int> >ans;
int main(){
scanf("%d%s",&n,str+1);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
pre[i]=i-1;next[i]=i+1;
}
for(int i=1;i<n;i++){
if(str[i]!=str[i+1])
que.push(Node(i,i+1,abs(a[i]-a[i+1])));
}
while(!que.empty()){
Node cur=que.top();que.pop();
if(flag[cur.l]||flag[cur.r]) continue;
ans.pb(mp(cur.l,cur.r));
int l=pre[cur.l],r=next[cur.r];
flag[cur.l]=flag[cur.r]=1;
next[l]=r;pre[r]=l;
if(l<1||r>n) continue;
if(str[l]!=str[r]){
que.push(Node(l,r,abs(a[l]-a[r])));
}
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)
printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
补充:软件开发 , C++ ,