重庆免费注册推广网站培训网

题目描述

有 n 个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为 ABCD，那么 BC 出列之后队伍变为 AD）。舞蹈技术相差最小即是 ai​ 的绝对值最小。

任务是模拟以上过程，确定跳舞的配对及顺序。

输入格式

第一行一个正整数 n 表示队伍中的人数。

第二行包含 n 个字符 B 或者 G，B 代表男，G 代表女。

第三行为 n 个整数 ai​。所有信息按照从左到右的顺序给出。

输出格式

第一行一个整数表示出列的总对数 k。

接下来 k 行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右 1 至 n 编号）。请先输出较小的整数，再输出较大的整数。

输入输出样例

输入 #1复制

4
BGBG
4 2 4 3

输出 #1复制

2
3 4
1 2

说明/提示

对于 50% 的数据，1≤n≤200。

对于 100% 的数据，1≤n≤2×105，0≤ai​≤107

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Pair {
    int idx1, idx2;
    int diff;
    bool operator<(const Pair& other) const {
        if (diff != other.diff) return diff < other.diff;
        return idx1 < other.idx1;
    }
};

int main() {
    int n;
    cin >> n;
    
    string genders;
    cin >> genders;
    
    vector<int> skills(n);
    for (int i = 0; i < n; i++) {
        cin >> skills[i];
    }
    
    vector<int> original_indices(n);
    for (int i = 0; i < n; i++) {
        original_indices[i] = i + 1;
    }
    
    vector<pair<int, int> > result;
    
    while (true) {
        vector<Pair> candidates;
        int current_size = genders.size();
        
        for (int i = 0; i < current_size - 1; i++) {
            if (genders[i] != genders[i + 1]) {
                Pair p;
                p.idx1 = i;
                p.idx2 = i + 1;
                p.diff = abs(skills[i] - skills[i + 1]);
                candidates.push_back(p);
            }
        }
        
        if (candidates.empty()) break;
        
        sort(candidates.begin(), candidates.end());
        Pair selected = candidates[0];
        
        int idx1 = selected.idx1;
        int idx2 = selected.idx2;
        
        result.push_back(make_pair(original_indices[idx1], original_indices[idx2]));
        
        genders.erase(idx1, 2);
        skills.erase(skills.begin() + idx1, skills.begin() + idx1 + 2);
        original_indices.erase(original_indices.begin() + idx1, original_indices.begin() + idx1 + 2);
    }
    
    cout << result.size() << endl;
    for (int i = 0; i < result.size(); i++) {
        int a = result[i].first;
        int b = result[i].second;
        cout << (a < b ? a : b) << " " << (a < b ? b : a) << endl;
    }
    
    return 0;
}