luogu 1327 数列排序 & 2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 J题 循环节
2024-08-31 07:22:08
luogu 1327 数列排序
题意
给定一个数列\(\{an\}\),这个数列满足\(ai≠aj(i≠j)\),现在要求你把这个数列从小到大排序,每次允许你交换其中任意一对数,请问最少需要几次交换?
思路
找循环节。答案即为 (循环节的长度\(-1\)) 对所有循环节求和。
如果只能交换相邻两个,那么就是求逆序对个数。因为交换相邻两个数字的效果是使逆序对个数\(-1\).
Code
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
int a[maxn], b[maxn];
bool vis[maxn];
map<int, int> mp;
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
b[i] = a[i];
mp[a[i]] = i;
}
sort(b, b+n);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
int j = i;
while (!vis[j]) {
vis[j] = true;
j = mp[b[j]];
++ans;
}
--ans;
}
printf("%d\n", ans);
return 0;
}
2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 J.Minimum Distance in a Star Graph
题意
给出一个排列,问对其进行多少次操作能得到递增的排列。
一次操作指交换第\(i\)个位置上的数和第\(1\)个位置上的数。
思路
找循环节。
对于包含第一个数字的循环节,交换次数为 (循环节长度\(-1\));\(otherwise\),交换次数为 (循环节长度\(+1\)).
Code
#include <bits/stdc++.h>
using namespace std;
#define maxn 1010
int n;
char s[100], t[100];
int pos[maxn];
bool vis[maxn];
void work() {
char ch;
memset(vis, 0, sizeof(vis));
memset(pos, 0, sizeof(pos));
scanf("%s%s", s, t);
for (int i = 0; i < n; ++i) pos[s[i]] = i;
int temp = 0, ans = 0; vis[0] = true;
while (t[temp] != s[0]) {
temp = pos[t[temp]];
++ans;
vis[temp] = true;
}
for (int i = 1; i < n; ++i) {
if (!vis[i]) {
vis[i] = true;
int temp = i, len = 0;
while (t[temp] != s[i]) {
temp = pos[t[temp]];
++len;
vis[temp] = true;
}
if (len) ans += len + 2;
}
}
printf("%d\n", ans);
}
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < 5; ++i) work();
}
return 0;
}
最新文章
- python 模块基础介绍
- 广搜+打表 POJ 1426 Find The Multiple
- Microsoft.ACE.OLEDB.12.0 错误 上传读取Excel错误
- cimge 这次能够图片大小尺寸
- LA 6450 Social Advertising
- ubuntu 下关闭MySql server
- 面向对象的方式进行数据交换网络之间的差异--无缝切换的发展到单机游戏C/S模式
- nfs+rsync+inotify实现文件的实时同步
- Sqlserver如何递归查询层级数据将父级字段和本级某个字段合并?如何自定义用户函数并调用?
- 解决ios不支持按钮:active伪类的方法
- 依赖背包——cf855C好题
- WebWorker与WebSocket实现前端消息总线
- pytorch预训练
- LinQ是什么?
- 咏南中间件JSON序列类
- sftp服务器的安装与远程
- php notes
- Path Sum II - LeetCode
- jenkins Email-ext plugin插件中Pre-send Script设置说明
- 简单实现MemCachedUtil