| 题目名称 | 1491. [UVa 11077] 排列统计 |
|---|---|
| 输入输出 | findpermutations.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-01-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：12， 通过率：66.67% | ||||
 AAAAAAAAAA |
100 | 0.000 s | 0.00 MiB | C++ |
 Go灬Fire |
100 | 0.003 s | 0.30 MiB | C++ |
 delta |
100 | 0.004 s | 0.30 MiB | C++ |
 cstdio |
100 | 0.004 s | 0.31 MiB | C++ |
 KZNS |
100 | 0.009 s | 0.39 MiB | C++ |
 mikumikumi |
100 | 0.039 s | 0.35 MiB | C++ |
|
mikumikumi |
100 | 0.052 s | 0.40 MiB | C++ |
|
mikumikumi |
100 | 0.056 s | 0.40 MiB | C++ |
|
delta |
20 | 0.004 s | 0.30 MiB | C++ |
|
KZNS |
20 | 0.010 s | 0.32 MiB | C++ |
| 关于 排列统计 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
难道不是“基于比较”的排序的下界为O(n*lg(n))么...至少n*lg(n)次交换是什么鬼啊...至少n*lg(n)次比较才对吧
  rvalue
2017-03-30 20:11
1楼
| ||||
1491. [UVa 11077] 排列统计
★☆ 输入文件：findpermutations.in
输出文件：findpermutations.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
排序是生活中最常见的操作之一，计算机科学对此大有用武之地。稍有常识的人都知道，基于交换的排序时间复杂度下界是O(nlogn)。这意味着可能设计出的最好排序算法将用至少O(nlog(n))次交换操作来给n个整数排序。虽然如此，对给定的n个整数，如果你知道每个数在排序后的位置，那么你总能找到一个包含至多n-1次交换的操作序列来将它们按升序排列。考虑四个元素<1 2 3 4>，有24种可能的排列，并且你知道每个元素在排序后的位置。
如果排列是<2 1 4 3>，至少需要进行2次交换来让它有序（分别交换1,2和4,3）。如果排列是<2 3 4 1>，就至少需要进行3次交换。<4 2 3 1>需要1次交换，<1 2 3 4>不需要交换。用这种方法，我们可以找到包含N个不同整数，并且至少交换K次才能排序的排列数。
【输入格式】
输入包含最多250组数据。
每组数据占1行，含2个正整数N(1<=N<=21)和K(0<=K<N)。
输入结束标志为N=K=0.
【输出格式】
对于每组数据，输出至少交换K次才能排序的排列数。
【样例输入】
3 1 3 0 3 2 0 0
【样例输出】
3 1 2
【来源】
UVa 11077 Find the Permutations
刘汝佳，《算法竞赛入门经典训练指南》表2-10
Problemsetter: Md. Kamruzzaman
Special Thanks: Abdullah-al-Mahmud