思路:
对于一个数字排列而言,加1,相当于得到大于该数字的最小数的排列;
以12543为例,如何得到大于该数的最小数呢?
我们从右往左看,找到第一处arr[i - 1] < arr[i],将arr[i - 1]与一个合适的位置交换,使得其大于原数且最小,
显然我们应该在arr[i]的右边找到一个大于arr[i - 1]且局部最小的数.(参考闫总视频图解)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 5;
int n,m;//n和m分别表示手指数和要加上的数字
int arr[N];//存有当前手指排列
int main () {
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> arr[i];
while (m--) {
int i = n;
while (i > 0 && arr[i] < arr[i - 1]) i--;
int t = i;
while (arr[t] > arr[i - 1]) t++;
swap(arr[i - 1],arr[t - 1]);
reverse(arr + i,arr + n + 1);
}
for (int i = 1;i <= n;i++) cout << arr[i] << ' ';
return 0;
}