UVA10570-Meeting with Aliens(枚举)
2024-10-15 16:17:58
Problem UVA1616-Caravan Robbers
Accept: 531 Submit: 2490
Time Limit: 3000 mSec
Problem Description
Input
Input will start with a positive integer, N (3 ≤ N ≤ 500) the number of aliens. In next few lines there will be N distinct integers from 1 to N indicating the current ordering of aliens. Input is terminated by a case where N = 0. This case should not be processed. There will be not more than 100 datasets.
Output
For each set of input print the minimum exchange operations required to fix the ordering of aliens.
Sample Input
4
1 2 3 4
4
4 3 2 1
4
2 3 1 4
0
1 2 3 4
4
4 3 2 1
4
2 3 1 4
0
Sample Output
0
0
1
题解:这个题很有价值。想到倍长数列是比较自然的,但是接下来怎么办,如何快速求出将一个序列排成有序的最小交换次数,这里要用到一个结论:对于一个长度为n的元素互异的序列,通过交换实现有序的最小的交换次数是=n - n被分解成单循环的个数。具体证明见如下博客:
https://blog.csdn.net/wangxugangzy05/article/details/42454111
明白了这个,题目就变得很简单了,枚举起点,dfs找环,取最大值得出结果,这里要注意一点就是序列既可以是升序,也可以是降序,因此要倒着再枚举一遍,方法不变。
#include <bits/stdc++.h> using namespace std; const int maxn = + ; int n;
int num[maxn << ];
bool vis[maxn]; void dfs(int st, int a) {
if (vis[a]) return;
vis[a] = true;
dfs(st, num[st + a - ]);
} void dfs2(int st, int a) {
if (vis[a]) return;
vis[a] = true;
dfs2(st, num[st - a + ]);
} int main()
{
//freopen("input.txt", "r", stdin);
while (~scanf("%d", &n) && n) {
for (int i = ; i < n; i++) {
scanf("%d", &num[i]);
num[i + n] = num[i];
} int Max = ; for (int st = ; st < n; st++) {
memset(vis, false, sizeof(vis));
int cnt = ;
for (int i = st; i < st + n; i++) {
if (!vis[num[i]]) {
dfs(st, num[i]);
cnt++;
}
}
Max = Max > cnt ? Max : cnt;
} for (int st = * n - ; st >= n; st--) {
memset(vis, false, sizeof(vis));
int cnt = ;
for (int i = st; i >= st - n + ; i--) {
if (!vis[num[i]]) {
dfs2(st, num[i]);
cnt++;
}
}
Max = Max > cnt ? Max : cnt;
} printf("%d\n", n - Max);
}
return ;
}
最新文章
- [LeetCode] One Edit Distance 一个编辑距离
- DirectAccess
- x01.os.8: 加载内核
- JAVA基础学习之final关键字、遍历集合、日期类对象的使用、Math类对象的使用、Runtime类对象的使用、时间对象Date(两个日期相减)(5)
- 如果在代码中使用JS
- (转)WPF控件开源资源
- VS为VC++添加UAC控制(VC程序默认管理员运行)
- cvWaitKey
- j-query j-query
- Memcached 实例
- 关于DatePicker控件在IsEnabled为False视觉效果没有明显辨识度的处理方法
- c++primerplus(第六版)编程题——第4章(复合类型)
- 大脑皮层是如何工作的 《人工智能的未来》(<;On intelligence>;)读书笔记
- linux下无ifconfig命令
- 读书笔记—CLR via C#字符串及文本
- Entity Framework技巧系列之五 - Tip 16 – 19
- 来杯咖啡看Pecan
- windows的github教程
- BBS项目详解(forms快速创建登陆页面,登陆验证、通过阅读器进行头像上传的预览、内存管理器)
- [Java]JGit用法总结