共计 1156 个字符,预计需要花费 3 分钟才能阅读完成。
题目粗心:
给出 0, 1.. N- 1 的一个序列,要求通过两两替换的形式将其变为递增序列,然而规定每次只能用 0 与其余数进行替换。求最小替换次数。
算法思路:
依据题目给出的替换例子,仔细观察能够晓得其替换策略为:如果数字 0 以后在 i 号位,则找到数字 i 以后所处的地位,而后把 0 与 i 进行替换。然而认真思考发现如果数字 0 在 0 地位就无奈继续执行上来,所以对于该策略,须要对于数字 0 在地位 0 上进行特判,将数字 0 与序列中任意一个不在本位上的数字进行替换,这样策略就能够持续进行上来,直到数字 0 在 0 地位上,并且其余数字都在其本位阐明替换完结。因为每一次替换都会一个数字放到本位 (数字 0 在 0 地位除外),根本能够认为这就是替换次数最小的策略
提交后果:
第一次测试:测试点 1 和 2 超时,起因是每次查找不在本位上的数字都是从头去找。
解决办法:应用数字 j 保留不在本位上的最小数字,初始为 0,而后都与 j 进行替换,那么每次遇到 0 在本位上的时候,就能够和间接从 j 进行查找最小的不在本位上的数字,因为小于数字 j 的都曾经在本位上了。
留神点:
1、建设数字到下标的映射会比拟不便操作,因为每一次都须要找到下标,并且下标的替换也就相当于是数字的替换。
2、应用一个数字记录上一次替换中不在本位上的最小数字 j,这样在数字 0 在本位寻找不在本位上的数字的时候就能够从 j 开始找,不然测试点 1 和 2 会超时。
3、此题尽管题目不难理解,然而实现过程是真的心累 ((╥╯^╰╥)),特地容易呈现死循环。
AC 代码:
#include <cstdio> | |
#include <algorithm> | |
using namespace std; | |
int main(){ | |
int N; | |
scanf("%d",&N); | |
int indexs[N];// 保留所有数字对应的地址 | |
int a; | |
for (int i = 0; i < N; ++i) {scanf("%d",&a); | |
indexs[a] = i;// 数字 a 的地位为 i | |
} | |
int num = 0;// 替换次数 | |
int j = 0;// 不在本位上的最小数字 | |
while (true){ | |
// 首先判断以后数字 0 是否在 0 地位上 | |
if(indexs[0]==0){ | |
// 找到任意一个不在本位上的数字 i 与 0 进行替换 | |
bool isAllinPosition = true;// 是否所有的数字都在本位上 | |
int i = 1; | |
for (; j < N; ++j) {if(indexs[j]!=j){ | |
i = j; | |
isAllinPosition = false; | |
break; | |
} | |
} | |
if(isAllinPosition) break; | |
swap(indexs[i],indexs[0]); | |
++num; | |
} else {// 将数字 0 和数字 indexs[0] 进行替换 | |
swap(indexs[0],indexs[indexs[0]]); | |
++num; | |
} | |
} | |
printf("%d",num); | |
return 0; | |
} |
正文完