以c++写一个代码:要求给出序列A和序列B,判断序列B是否序列A经过m趟插入排序后得到的非降序结果。是的话,给出序列A第m+1趟插入排序的结果。不是的话,给出序列A第m趟插入排序的结果。 输入格式: 输入有三行: 第一行是n值和m值,表示序列的元素个数以及排序趟数。1<=n<=10000, 1<=m<n-1. 第二行是序列A的n个元素。 第三行是序列B的n个元素。 输出格式: 输出有两行: 第一行是YES或NO,表示B是否A第m趟插入排序的结果。 第二行是n个数,表示第m+1趟或第m趟插入排序的结果。 行末不能有空格。
时间: 2024-03-20 14:39:01 浏览: 56
以下是代码实现,实现了题目要求的功能:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m;
int a[N], b[N], c[N];
bool check() // 判断序列B是否是序列A经过m趟插入排序后得到的非降序结果
{
for (int i = 0; i < n; i++)
if (a[i] != b[i]) return false;
return true;
}
void insert_sort(int l, int r) // 插入排序
{
for (int i = l + 1; i <= r; i++)
{
int j = i;
while (j > l && c[j] < c[j - 1])
{
swap(c[j], c[j - 1]);
j--;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i];
c[i] = a[i];
}
for (int i = 0; i < n; i++) cin >> b[i];
if (check()) // 序列B是序列A经过m趟插入排序后得到的非降序结果
{
cout << "YES" << endl;
insert_sort(0, m);
for (int i = 0; i < n; i++) cout << c[i] << endl;
}
else // 序列B不是序列A经过m趟插入排序后得到的非降序结果
{
cout << "NO" << endl;
for (int i = 0; i <= m; i++) insert_sort(i * (n - 1) / m, (i + 1) * (n - 1) / m);
for (int i = 0; i < n; i++) cout << c[i] << endl;
}
return 0;
}
```
具体思路如下:
首先输入序列A和序列B,保存在数组a和b中。
然后判断序列B是否是序列A经过m趟插入排序后得到的非降序结果,如果是,就对序列A进行前m趟插入排序,得到第m+1趟插入排序的结果,并输出YES和第m+1趟插入排序的结果;如果不是,就对序列A进行前m趟插入排序和第m+1趟插入排序,得到第m趟插入排序的结果,并输出NO和第m趟插入排序的结果。
其中,判断是否非降序可以直接比较数组a和b的元素是否相同。对于插入排序,可以用一个新数组c记录a的元素,然后对c进行排序。第m+1趟插入排序的排序区间是0~m,前m趟插入排序的排序区间是i*(n-1)/m~(i+1)*(n-1)/m,其中i从0到m-1。
阅读全文