Codeforces Global Round 9 E. Inversion SwapSort
2024-08-31 23:54:20
题目链接:https://codeforces.com/contest/1375/problem/E
题意
给出一个大小为 $n$ 的数组 $a$,对数组中的所有逆序对进行排序,要求按照排序后的顺序交换每一对逆序对后数组为非递减数组。
题解
先将顺组的下标按元素大小排为非递减序,此即交换完所有的逆序对后得到的下标序列。
再对下标序列进行冒泡排序还原到初始时的 $0, 1, 2, \dots, n - 1$,冒泡排序中的交换顺序即为逆序对的排列顺序。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
int a[n] = {};
for (int i = 0; i < n; i++)
cin >> a[i];
int p[n] = {};
iota(p, p + n, 0);
sort(p, p + n, [&] (int x, int y) {
if (a[x] != a[y]) return a[x] < a[y];
else return x < y;
});
vector<pair<int, int>> res;
for (int i = 0; i < n; i++) {
for (int j = 0; j + 1 < n; j++) {
if (p[j] > p[j + 1]) {
res.emplace_back(p[j + 1], p[j]);
swap(p[j], p[j + 1]);
}
}
}
cout << res.size() << "\n";
for (auto i : res)
cout << i.first + 1 << ' ' << i.second + 1 << "\n";
}
最新文章
- Microservice Anti-patterns
- 使用 SWFObject.js 插入Flash
- C# DataGrid根据某列的内容设置行字体加粗 单元格设置对齐方式
- c# 函数
- CAShaperLayer的应用
- JavaScript排序算法——堆排序
- const 和宏的区别
- Linux主流發行版本介紹
- 002--VS C++ 获取鼠标坐标并显示在窗口上
- 将Ojective-C代码移植转换为Swift代码
- 大数据处理N!(21<;N<;2000)
- 移动基于Percona XTRADB Cluster的大数据解决方式
- ubuntu重启+sublime快捷键
- Kafka学习入门
- ado.net中事务的使用
- scrapy实战--登陆人人网爬取个人信息
- 【BZOJ1568】[JSOI2008]Blue Mary开公司 线段树
- cratedb joins 原理(官方文档)
- df -h 卡死 如何解决
- C#.net开发 List与DataTable相互转换 【转】