P1088 火星人
taozhengxing
·
·
个人记录
[NOIP2004 普及组] 火星人
** 第一次提交题解 不喜勿喷 ~~~~ **
题目描述
以下省略部分
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
输入格式
共三行。
第一行一个正整数 N，表示火星人手指的数目（1 \le N \le 10000）。
第二行是一个正整数 M，表示要加上去的小整数（1 \le M \le 100）。
下一行是 1 到 N 这 N 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。
输出格式
## 样例 #1
### 样例输入 #1
```
5
3
1 2 3 4 5
```
### 样例输出 #1
```
1 2 4 5 3
```
## 提示
对于 $30\%$ 的数据，$N \le 15$。
对于 $60\%$ 的数据，$N \le 50$。
对于 $100\%$ 的数据，$N \le 10000$。
这道题主要是排列
全排列
过程都在代码里哦
_主要是遍历数组、找拐点，还要防止越界~_
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[10005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
while(m--){ // 数 3个数
int k= n; //末端位置
// 从后往前 前一位和后一位比较
while( a[k-1]>a[k]) k--; // 从后往前 找拐点
k--; // 拐点位置
int t= k;
// t+1 拐点右侧 找到最后一个大于拐点的值 防止 t+1 越界
while(t+1<=n&&a[t+1]>=a[k]) t++;
swap(a[t],a[k]); //交换k拐点 和 右侧
reverse(a+k+1,a+n+1); // 翻转k拐点右侧区间
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
```