A49760. 部分排序程序命名：sort.cpp
填空题
中等
知识点
题目描述
部分排序
程序命名：sort.cpp
题目描述
一个数列P中有n个数。小蓝从中选择位置连续的k个数，并对这k个数进行升序排列。求排序后的数列有多少种？
输入
n k
P0 P1...Pn-1
其中：所有的輸入都是整数，2<=n<=100 , 2<=k<=n , 0<=Pi<=n-1 ，
P0，P1，..Pn-1数值都不相同。
输出
部分排序后数列的排列数。
样例输入
5 3
0 2 1 4 3
样例输出
2
样例说明：从原数列抽取连续3个数排序后有2种可能性：（0，1，2，4，3）和（0，2，1，3，4）
参考答案
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
//b记录本次排序后的数列
//last记录上次排序得到的数列
int a[N], b[N], last[N];
int n, k;
//检查两个数列是否相同
bool check(int a[], int b[])
{
for(int i = 0; i < n; i ++)
if(a[i] != b[i]) return false;
return true;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> a[i];
//将原数列a拷贝到last中
memcpy(last, a, sizeof a);
int sum = 0;
//枚举所有连续k个数的起始位置
for(int i = 0; i <= n - k; i ++)
{
//将a拷贝到b中进行排序
memcpy(b, a, sizeof a);
sort(b + i, b + i + k);
//排序后与上一个序列不相同
if(!check(last, b)) sum ++;
//将b拷贝到last
memcpy(last, b, sizeof b);
}
cout << sum << endl;
return 0;
}
上一题
下一题