社区讨论
0pts,求条
P1878舞蹈课参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mljgsh08
- 此快照首次捕获于
- 2026/02/12 20:58 4 周前
- 此快照最后确认于
- 2026/02/15 14:10 3 周前
0pts,求条
Code
CPP
Code#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5;
int a[N + 5], n;
int nxt[N + 5], prv[N + 5], male[N + 5];
bool vis[N + 5];
pair<int, int> ans[N + 5];
struct Node {
pair<int, int> connection;
int subabs;
};
bool operator < (Node x, Node y) {
if (x.subabs != y.subabs) return x.subabs > y.subabs;
return x.connection.first > y.connection.first;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
char opt;
cin >> opt;
if (opt == 'B')
male[i] = 1;
else
male[i] = 2;
}
priority_queue<Node> heap;
for (int i = 1; i <= n; i ++)
cin >> a[i];
// Initalize Min-heap
for (int i = 1; i < n; i ++)
if (male[i] != male[i + 1])
heap.push({{i, i + 1}, abs(a[i] - a[i + 1])});
// Initalize Linked-list
for (int i = 1; i <= n; i ++)
nxt[i] = i + 1, prv[i] = i - 1;
// Solve
int curr = 0;
while (!heap.empty()) {
Node t = heap.top();
heap.pop();
int p = t.connection.first, q = t.connection.second;
if (vis[p] == 0 && vis[q] == 0) {
nxt[prv[p]] = nxt[q];
prv[nxt[q]] = prv[p];
ans[++ curr] = {p, q};
vis[p] = vis[q] = 1;
if (vis[prv[p]] == 0 && vis[nxt[q]] == 0)
if (male[prv[p]] == 2 && male[nxt[q]] == 1)
heap.push({{prv[p], nxt[q]}, abs(a[nxt[q]] - a[prv[p]])});
}
}
// Print
cout << curr << endl;
for (int i = 1; i <= curr; i ++)
cout << ans[i].first << " " << ans[i].second << endl;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...