Codeforces Global Round 11 D. Unshuffling a Deck(构造/相邻逆序对)
2024-09-01 16:16:38
题目链接:https://codeforces.com/contest/1427/problem/D
题意
给出一个大小为 \(n\) 的排列,每次操作可以将 \(n\) 个数分为 \(1 \sim n\) 个非空连续份,然后将对称的份两两交换,试给出在 \(n\) 次操作内将排列排为升序的操作过程。
题解
- 找到值相差为 \(1\) 的逆序对:\(i<j\),\(a_i = a_j + 1\)
- 将已为升序的数视为一个整体,找到 \(t\) 满足 \(i \le t < j\),\(a_t > a_{t+1}\)
- 分为 \(4\) 份,\(D_1=[a_1,a_2,\dots,a_{i-1}],\ D_2=[a_i,a_{i+1},\dots, a_t],\ D_3=[a_{t+1},a_{t+2},\dots, a_j],\ D_4=[a_{j+1},a_{j+2},\dots, a_n]\)
- 将对称组交换,转至步骤 \(1\) 。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), pos(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
}
vector<vector<int>> ans;
while (not is_sorted(a.begin(), a.end())) {
for (int i = 0; i < n; i++) {
pos[a[i]] = i;
}
//1
for (int i = 1; i < n; i++) {
if (pos[i] < pos[i - 1]) {
//2
int l = pos[i];
int r = pos[i - 1];
int mid = l;
while (a[mid + 1] == a[mid] + 1) ++mid;
//3
ans.push_back({l, mid - l + 1, r - mid, n - r - 1});
//4
vector<int> b;
for (int i = r + 1; i < n; i++) b.push_back(a[i]);
for (int i = mid + 1; i < r + 1; i++) b.push_back(a[i]);
for (int i = l; i < mid + 1; i++) b.push_back(a[i]);
for (int i = 0; i < l; i++) b.push_back(a[i]);
a.swap(b);
break;
}
}
}
cout << ans.size() << "\n";
for (auto &v : ans) {
//每份非空
while (v.back() == 0) v.pop_back();
while (v.front() == 0) v.erase(v.begin());
cout << v.size() << "\n";
for (int i = 0; i < int(v.size()); i++) {
cout << v[i] << " \n"[i == int(v.size()) - 1];
}
}
return 0;
}
最新文章
- JWT实现token-based会话管理
- [转]HttpModule的认识
- response项目的各个写法
- c#事务用法
- 解决在IE下LABEL中IMG图片无法选中RADIO的几个方法
- SWFUpload使用指南
- c++类使用
- 【转载】Powershell在世纪互联Office365中批量将用户添加到组
- 6月A项目的总结
- vultr vps2016年免费升级流量和cpu
- Kindeditor编辑插件的使用
- linux CentOS部署【minimal 】
- (NO.00003)iOS游戏简单的机器人投射游戏成形记(八)
- Scrapy爬虫框架第五讲(linux环境)【download middleware用法】
- Linux性能评估工具
- fail2ban 防爆破,防止CC 攻击
- Python+OpenCV图像处理(十六)—— 轮廓发现
- onOptionsItemSelected、onMenuItemSelected、onContextItemSelected 区别
- 前端打包文件在 nginx 上 403 的解决办法
- Oracle事务与锁
热门文章
- 第8章 控制对象的访问(setter、getter、proxy)
- three.js canvas内场景生成图片 canvas生成图片
- 【Flutter】可滚动组件之滚动控制和监听
- Podinfo,迷你的 Go 微服务模板
- MATLAB中load和imread的读取方式区别
- HTML部分
- Navicat 创建mysql存过、定时执行存过
- https://dev.mysql.com/doc/refman/8.0/en/savepoint.html
- git commit,启动文本编辑器
- c 越界 数组越界