思路
题目要求:“按跳舞顺序输出”,也就是在处理过程保持输出顺序不变,用标记替代删除是最简单的做法。
把数据导入小根堆,就可以取出最小的,在把取出的放入答案数组,并统计个数。ok
流程
1、设计pair变量存储答案,cnt统计答案数量。pair<int,int> ans[N]; int cnt
2、字符数组char s[N];
收集输入的字符,int n,d[N]
收集人数和舞技值。
3、bool vis[N],f[N];
vis标记是否用过,f标记男女
4、把放在d数组的数据在小根堆里面过一下,就可以取出“舞蹈技术相差最小的那一对”,在利用vis和f检查一下相邻的是否能够凑成一对,是的话放入小根堆。
struct node{//小根堆
int x,y,z;
friend bool operator >(const node& a,const node& b){
return a.z>b.z || (a.z==b.z&&a.x>b.x);
}
};
priority_queue<node,vector<node>,greater<node> > q;
代码
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int N=2e5+10;
pair<int,int> ans[N];//存答案
int n,d[N],cnt;//d存储舞技值,cnt存答案数
char s[N];
bool vis[N],f[N];//vis是否存过,f判断男女
struct node{//小根堆
int x,y,z;
friend bool operator >(const node& a,const node& b){
return a.z>b.z || (a.z==b.z&&a.x>b.x);
}
};
priority_queue<node,vector<node>,greater<node> > q;
int main(){
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++){
if(s[i]=='B') f[i]=true;//男
}
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
for(int i=2;i<=n;i++){
if(f[i-1]!=f[i]){
q.push((node){i-1,i,abs(d[i-1]-d[i])});
}
}
while(!q.empty()){
int x=q.top().x;
int y=q.top().y;
q.pop();
if(!vis[x]&&!vis[y]){
vis[x]=true;
vis[y]=true;
ans[++cnt].first=x;
ans[cnt].second=y;
while(x>=1&&vis[x]) x--;//可以穿过标记为真的数据
while(y<=n&&vis[y]) y++;
if(x>=1&&y<=n&&f[x]!=f[y]){
q.push((node){x,y,abs(d[x]-d[y])});//强转为node类型
}
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++){
printf("%d %d\n",ans[i].first,ans[i].second);
}
return 0;
}
备注
(node){x,y,abs(d[x]-d[y])}
这种强转node类型的做法不知道在noilinux中可以使用吗?
答:这种强转结构体的方法,经过实测noilinux,可以用。