发布建设网站,黑河市建设局网站,某集团网站建设规划书,布恩网站删除题目描述
有 n 个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始#xff0c;他们从左到右站成一排。当这一排中至少有一对相邻的异性时#xff0c;舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对#xff0c;那么最左边的那一对出列。一对异性出…题目描述
有 n 个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始他们从左到右站成一排。当这一排中至少有一对相邻的异性时舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对那么最左边的那一对出列。一对异性出列之后队伍中的空白按原顺序补上即若队伍为 ABCD那么 BC 出列之后队伍变为 AD。舞蹈技术相差最小即是 ai 的绝对值最小。
任务是模拟以上过程确定跳舞的配对及顺序。
输入格式
第一行一个正整数 n 表示队伍中的人数。
第二行包含 n 个字符 B 或者 GB 代表男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×1050≤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; vectorint skills(n); for (int i 0; i n; i) { cin skills[i]; } vectorint original_indices(n); for (int i 0; i n; i) { original_indices[i] i 1; } vectorpairint, int result; while (true) { vectorPair 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; }
