| 题目名称 | 1032. [焦作一中2012] 最小交换排序(无数据) |
|---|---|
| 输入输出 | minsort.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 田劲锋
于2012-08-21加入修改该题
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：17， 提交：29， 通过率：58.62% | ||||
|
sqyon |
100 | 0.087 s | 1.84 MiB | C++ |
|
OEE_ZFF |
100 | 0.104 s | 1.08 MiB | C++ |
|
qxj |
100 | 0.104 s | 1.94 MiB | C++ |
|
陈鹏光 |
100 | 0.128 s | 1.02 MiB | Pascal |
|
zsj |
100 | 0.128 s | 4.40 MiB | C++ |
|
羽 |
100 | 0.141 s | 1.08 MiB | C++ |
|
Pine |
100 | 0.160 s | 0.88 MiB | C++ |
|
祝一帆 |
100 | 0.188 s | 0.69 MiB | C++ |
|
svideo |
100 | 0.209 s | 1.66 MiB | C++ |
|
whw |
100 | 0.218 s | 2.60 MiB | C++ |
| 关于 最小交换排序(无数据) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
做了100000的数据，发现模拟快的飞起。。。。。。
| ||||
【题目描述】
小$x$最近切了一道很水的排序题，但是在$AC$之后，他想到了一个问题：
给定$n$个互不相等的整数序列，每次可以对任意一对数进行交换，请问：至少交换多少次才能使序列严格递增？
【输入格式】
第一行：一个整数$n$;
第二行：$n$个用空格隔开的正整数$a_i，-2^{31}<=a_i<=2^{31}-1$;
【输出格式】
一个整数，表示符合题意的最少交换次数；
【样例输入】
8 8 23 4 16 77 -5 53 100
【样例输出】
5
【数据规模与约定】
对于20%的数据，$n<=100$;
对于50%的数据，$n<=5000$;
对于100%的数据，$n<=100000$;
【来源】
$焦作一中2012$