社区讨论
求助
P1878舞蹈课参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lrbhkutl
- 此快照首次捕获于
- 2024/01/13 11:07 2 年前
- 此快照最后确认于
- 2024/01/13 14:13 2 年前
本蒟蒻看题解看半天打问号的那里没看懂而且代码也错了
CPP#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int N =200005;
struct Node{
int minus;
int l, r;
char ch;
int p;
}a[N];
priority_queue<Node> q;
int ans[N][2];
bool operator<(Node x, Node y){//对技术差值排序
if(x.minus == y.minus)
return x.p < y.p;
return x.minus < y.minus;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
cin >> a[i].ch;
int now, len = 0;
scanf("%d", &now);
for(int i = 1; i < n; i++){
int x;
scanf("%d", &x);
a[i].p = i;
a[i].minus = abs(now-x);//将差值放入当前位
a[i].l = i-1;
a[i].r = i+1;
q.push(a[i]);
now = x;
}
a[n].r = n+1, a[n].p = n, a[n].minus = 1e9; //最后一位没差值设最大
while(!q.empty()){
int x = q.top().p, k = q.top().minus;//当前位
q.pop();
int y = a[x].r;//当前后一位
if(a[x].minus == k && a[x].ch != a[y].ch && (y != n+1) && (x >= 1)){//若配对
ans[++len][0] = x, ans[len][1] = y;
a[a[x].l].minus += a[x].minus + a[y].minus;//更新此时差??
a[a[y].r].l = a[x].l;a[a[x].l].r = a[y].r;//重连
if(a[x].l > 0 && a[y].r < n)
q.push(a[a[x].l]);
a[x].l = a[x].r = 0, a[y].l = a[y].r = n+1;//断
}
}
printf("%d\n", len);
for(int i = 1; i <= len; i++)
printf("%d %d\n", ans[i][0], ans[i][1]);
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...