一开始提交的时候UKE了,我都惊呆了,从来没见过。后面又提交就全是wonderful answer了。
麻烦走过路过的dalao瞅瞅错误。
#include<bits/stdc++.h>
#define gc ch=getchar()
#define pt puts("")
#define pc putchar(32)
using namespace std;
template <class T>void read(T &s){
s=0;T f=1;char gc;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;gc;}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';gc;}
s*=f;
}
template <class T>void put(T s){
if(s<0) putchar('-'),s=-s;
if(s>9) put(s/10);
putchar(s%10+'0');
}
struct node{
int dis,pos1,pos2;
bool operator <(const node &x)const{
if(x.dis==dis) return x.pos1<pos1;
return x.dis<dis;
}
};
priority_queue<node> q;
queue<node> p;
int n,a[200005],b[200005],nxt[200005],lst[200005],vis[200005],ans;
int main(){
read(n);
for(int i=1;i<=n;++i){
char gc;
if(ch=='B') a[i]=1;
if(i<n) nxt[i]=i+1,lst[i+1]=i;
}
for(int i=1;i<=n;++i){
read(b[i]);
if(i>1&&a[i]!=a[i-1]) q.push((node){abs(b[i]-b[i-1]),i-1,i});
}
while(!q.empty()){
if(vis[q.top().pos1]||vis[q.top().pos2]){q.pop();continue;}
p.push(q.top()),++ans;
int X=q.top().pos1,Y=q.top().pos2;
q.pop();
vis[X]=vis[Y]=1;
nxt[lst[X]]=nxt[Y];
lst[nxt[Y]]=lst[X];
if(a[lst[X]]!=a[nxt[Y]]) q.push((node){abs(b[lst[X]]-b[nxt[Y]]),lst[X],nxt[Y]});
}
put(ans),pt;
while(!p.empty()) put(p.front().pos1),pc,put(p.front().pos2),pt,p.pop();
}
我发现洛谷的讨论区真的好可爱啊,连称呼都是“您”,爱了爱了~