算法
(堆) $O(n*log(n))$
我们可以用来记录每个点的上一个点和下一个点是什么,堆中记录的是每一对相邻的男女相差值和他们的位置,每次从中取出最小的一个,加到答案里,再将他们的上一个和下一个加到堆里,并改变指针数组。别忘了用$set$记录一下那些点已经用过,用过后存进$set$中,如果发现从堆中取出的点至少有一个已经用过的话,就$continue$.
C++ 代码
// codeforce每日一题 https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> PIII;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m;
char str[N];
int w[N], ne[N], pre[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>str + 1;
rep(i, 1, n) cin>>w[i], ne[i] = i + 1, pre[i] = i - 1;
set<int> s;
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
rep(i, 1, n - 1)
if(str[i]!=str[i+1])
heap.push({abs(w[i] - w[i + 1]), {i, i + 1}});
vector<PIII> res;
while(heap.size())
{
auto u = heap.top();
heap.pop();
if(s.count(u.se.fi) || s.count(u.se.se)) continue;
res.pd({u.fi,{u.se.fi, u.se.se}});
if(pre[u.se.fi]!=0 &&
ne[u.se.se]!=n+1 &&
str[pre[u.se.fi]]!=str[ne[u.se.se]])
heap.push({abs(w[pre[u.se.fi]] - w[ne[u.se.se]]), {pre[u.se.fi], ne[u.se.se]}});
pre[ne[u.se.se]] = pre[u.se.fi];
ne[pre[u.se.fi]] = ne[u.se.se];
s.insert(u.se.se);s.insert(u.se.fi);
}
// sort(all(res));
cout<<res.size()<<endl;
for(auto u : res) cout<<u.se.fi<<" "<<u.se.se<<endl;
return 0;
}
每次堆插入$O(logn)$,整体不应该是$O(nlogn)$么。。。?
不好意思,写错了