题目链接: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";
}

最新文章

  1. Microservice Anti-patterns
  2. 使用 SWFObject.js 插入Flash
  3. C# DataGrid根据某列的内容设置行字体加粗 单元格设置对齐方式
  4. c# 函数
  5. CAShaperLayer的应用
  6. JavaScript排序算法——堆排序
  7. const 和宏的区别
  8. Linux主流發行版本介紹
  9. 002--VS C++ 获取鼠标坐标并显示在窗口上
  10. 将Ojective-C代码移植转换为Swift代码
  11. 大数据处理N!(21&lt;N&lt;2000)
  12. 移动基于Percona XTRADB Cluster的大数据解决方式
  13. ubuntu重启+sublime快捷键
  14. Kafka学习入门
  15. ado.net中事务的使用
  16. scrapy实战--登陆人人网爬取个人信息
  17. 【BZOJ1568】[JSOI2008]Blue Mary开公司 线段树
  18. cratedb joins 原理(官方文档)
  19. df -h 卡死 如何解决
  20. C#.net开发 List与DataTable相互转换 【转】

热门文章

  1. Petalinux和Vivado的安装
  2. 解决Cannot find module &#39;@angular/compiler-cli&#39;
  3. JavaScript中的原型、原型链、原型模式
  4. 【Oracle】 并行查询
  5. CTFHub - Web(六)
  6. 24V转5V芯片,高输入电压LDO线性稳压器
  7. .NET Core 问题记录
  8. 【JeecgBoot】关于 jeecg-boot 的项目理解、使用心得和改进建议
  9. Android N selectQualifiedNetwork分析
  10. Redis布隆过滤器与布谷鸟过滤器