AcWing 420. 火星人
原题链接
中等
作者:
BBlone
,
2024-01-25 16:20:32
,
所有人可见
,
阅读 33
求序列的下一个比他字典序大的序列
算法1
java实现next_permutation() 直接找到他的下一个序列)(字典序小的)
//对于题目长的看抓住关键操作就行了
//理解题意 将问题转换 题意就是 N个数的字典序列从小的到达的排序 依次代表 1 2 3 4 5 6 这个数 让我们求下一个排列M次的序列
//也将是将序列排列M次 每次排列都是找比序列字典序大的最小的序列
//所以关键操作在于 如何找比一个比该序列大的最小序列
//这时候我们就要拿样例找两个序列之间的规律和关系
//对于一个由N个数构成的序列 字典序最小一定为递增序列 最小一定为递减
// 然后我们要找比这个序列大的最小的 那么我们要从右往左进行更改位置上的值
// 12345 这里其实有点贪心的感觉局部最优全局最优 但是依据思维我们肯定要找最低位上改为比他大的最小的一个数
// 12345 4找后面最低为比他大的最小的一个数 为 5 那么这个序列一定比前面大 那么我们让后面的序列最小就行了拉
// //那么如何照这个4 4有什么这个位置有什么性质呢 也就是 因为45这个序列 可以变得更大也就是从右往左找能变大的序列 不可能从左往右吗吧
// 5已经是很大的 所以我们要更改45 也就是后面有比4 大的数才可以变得更大 所以4后面的序列都是递减去的 ak-1<ak-1
// 所以我们已经有了步骤了
// 1. 从右往左找能够变大的序列 这个序列不是单调递减的 而开头是第一个ak-1<ak的位置 4 然后我们把这个位置变为比他大最小的数 然后后面递增排序
// 因为最短的一个可以变大的 说明 4的后面的序列一定是递减的 所以我们只需要反转就能递增
// 1. ak-1<ak 从右往左找
// 2 将ak 变为比他大的最小的一个 从后面序列找
// 3 将后面序列反转就行了
// 上面就是核心操作 也就是c++自带next_permutation()找到比序列字典序大的最小的序列 O(N)S时间复杂度
//理解题意转换问题 找核心操作 找方法解决
import java.util.*;
import java.io.*;
public class Main {
static int N=10010;
static int[] a=new int[N];
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n,m;
n=in.nextInt();
m=in.nextInt();
for(int i=0;i<n;i++){
a[i]=in.nextInt();
}
while(m!=0){ //执行m次
//从右往左
int ak=-1;
for(int k=n-2;k>=0;k--){
if(a[k]<a[k+1]){
ak=k;
break;
}
}
//找到ak后面比他大的最小值
int t=ak;
while(t+1<n&&a[t+1]>a[ak]) t++;
int tmp=a[t];
a[t]=a[ak];
a[ak]=tmp;
Arrays.sort(a,ak+1,n);
m--;
}
for(int i=0;i<n;i++){
System.out.print(a[i]+" ");
}
}
}
算法2
dfs 伪造现场 从当前状态出发