最短路

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 2e5 + 10;
 5 
 6 struct node
 7 {
 8     int l,r;
 9     int v;
10     bool operator<(const node &x) const {
11     if(x.v == v) return x.l < l;
12     return x.v < v;
13     }
14 };
15 priority_queue<node> q;
16 
17 int n;
18 char ch; //字符
19 bool bg[N]; //用来判断字符串数组是否为异性，是为异性就可以入堆
20 int a[N]; 
21 bool is[N]; //标记是否出现过
22 int l[N],r[N]; //表示两个端点的左右元素
23 vector<node> ans;
24 
25 int main()
26 {
27     cin >> n;
28     for (int i = 1; i <= n; i ++ ) cin >> ch,bg[i] = (ch == 'B' ? 1 : 0);
29     for (int i = 1; i <= n; i ++ ) cin >> a[i];
30     for (int i = 1; i <= n; i ++ ) l[i] = i - 1,r[i] = i + 1;
31     
32     is[0] = is[n + 1] = 1;
33     for (int i = 2; i <= n; i ++ ) //如果相邻为异性，丢到堆中，从小到大进行排序
34     if(bg[i] ^ bg[i - 1]) q.push({i - 1,i,abs(a[i - 1] - a[i])});
35     
36     while(!q.empty())
37     { //如果堆顶的元素两个端点之前出现过(已经被标记了)，那么没用直接删掉
38         while(!q.empty() && (is[q.top().l] || is[q.top().r])) q.pop(); 
39         if(q.empty()) break; //堆为空直接g；
40         node now = q.top(); //now 为堆顶的三个元素(a[i]元素下标)
41         q.pop(); //删掉并更新堆顶
42         int x = l[now.l],y = r[now.r]; // x为堆顶左端点的左边一个点,y同理
43         l[y] = x,r[x] = y; //让x,y互相相邻
44         if(bg[x] ^ bg[y]) q.push({x,y,abs(a[x] - a[y])}); //x,y互为异性丢到堆里面去
45         ans.push_back(now); //把堆顶的元素丢到 ans里面去
46         is[now.l] = 1,is[now.r] = 1; //标记堆顶两个端点出现过了
47         
48     }
49     cout << ans.size() << endl; //有多少对刚才插入的堆顶元素
50     for (auto i : ans ) cout << i.l << ' ' << i.r << endl; //输出每一组的左右端点
51     return 0;
52 }