哪位C语言大神看看这道题。用最简单易懂的方法解决，初学C语言 要注释 谢谢😊
游戏是这样的：
XxX_Stu给定一个正整数n。
然后再给Tamama一个长度为n的整数序列。
这个序列的数字为1、2......、n的排列。
Tamama可以进行一种操作：
选择序列中的一个数字，将这个数字放到序列中另外一个数字的前面或者后面。
最终目标是使得序列变成：1、2......、n。
但是这个游戏限制Tamama的操作次数，必须是最少！
举个栗子：
n = 6
原序列）2 4 3 5 6 1
第一次操作）把4放到3后面，得到：2 3 4 5 6 1
第二次操作）把1放到2前面，得到：1 2 3 4 5 6
输入
一个正整数T（0 < T < = 50 ），表示一共有T组数据。
对于每组数据：
一个正整数n（0 < n <= 1000），表示序列的长度。
接下来n个数字a[i]（0 < a[i] <= n ， 1 < = i <= n），
且a[i] != a[j] （ 1 < = i < j < = n ）。
（说白了不就是1到n的排列...真是的= =||。）
输出
对于每组数据：
输出一行，一个数字ans，表示Tamama做少操作多少次可以把序列变成1、2......、n的序列。
样例输入
2
5
1 2 3 4 5
6
2 4 3 5 6 1
样例输出
0
2 展开
这个题的难点在于怎么计算最小移动次数。
从举例来看，2 4 3 5 6 1，有一个特点，能够找到几组最大的基本有序的数列，如：2 3 5 6 或 2 4 5 6，这两组数列个数都为4个，那么只要移动剩下两个数字，就能用最小的移动次数来达成目标。
再找一个例子：10 5 6 1 4 7 8 2 3 9，其最大的基本有序数列为：5 6 7 8 9 或 1 4 7 8 9，那么最小移动次数为 10 - 5 = 5。
所以，可以把这个问题转化为寻找一组数列的基本有序数的最大个数。
一种简单的算法为：
先取第1个数，然后从第2个数开始取，只要比第1个数大，就取出来，然后继续往后面取数，只要满足比前面取到的数大，就取出来。最后会得出一组有序数列
记录这组有序数列的个数
从这组有序数列的最后一个数开始，把这个数去掉，然后再从这个数对应的原来数列的位置的后面开始取值，构成新的有序数。再记录其个数。重复删除这组数列的最后一个，直到删除到这组数列的第1个为止。
原序列中的第1个数组成的有序数统计结束，再取第2个数进行上面流程的统计。
上面一大段说的有点晕，举个例子，2 4 3 5 6 1。
按上面的算法处理，第1个取 2， 第2个 4， 第3个 不能取3，因为3比4小，所以取5，第4个取6。
所以第一个有序数列为 2 4 5 6
然后对取出来的数列进行删除处理，把6去掉，剩下 2 4 5 ，6在原来序列的倒数第2个位置，那么继续取值，6后面的数字是1，5比1大，不能取出来，所以新数列为 2 4 5
再对 2 4 5 进行删除操作，得到 2 4 ，5在原来位置的后面数字是6，可以取出来，形成新数列 2 4 6
再对 2 4 6 进行删除操作，得到 2 4 ，6在原来位置的后面数字是1，不能取，后面已经没值，新数列 2 4
再对 2 4 进行删除操作，得到 2，4在原来位置后面是3，可以取出来，再往后取5，取6，得到新数列2 3 5 6
后面就不再列出来了，反正就是从后往前遍历了，最后统计组成有序数列的数字个数最大的那个值。
最后再用N减去这个值，就是目标所要求的最小操作次数了。
说了一大堆，下面给出示例代码(代码里定义了一个debug，用来调试用的，手动输值太麻烦)：
#include <stdio.h>
#include<malloc.h>
#define debug 0
int allTest = 0;//记录所有测试项数量
void printAll(int **p){
//输出所有测试项数据，调试用。
int i,j;
for(i=0;i<allTest;i++){
printf("%d\n",p[i][0]);
for(j=1;j<=p[i][0];j++){
printf("%3d",p[i][j]);
}
printf("\n");
}
}
void inputN(int *p){
int i;
//录入一组N数列
for(i=1;i<=p[0];i++){
scanf("%d", &p[i]);
}
}
void input(int **p){
int i,n;
printf("请录入数据：\n");
scanf("%d", &allTest);
for(i=0;i<allTest;i++){
//录入一条测试数据，包括N的值及N的数列
//把N的值存储在 p[0] 中， p[i]存储数列的值。
scanf("%d", &n);
p[i] = malloc((n+1) * sizeof(int));
p[i][0] = n;
inputN(p[i]);
}
}
int maxSorted(int *p){
int i,j,k;
int max = 0;//最大有序数的个数
int count[p[0]], index;//count[]数组存储p数列的下标，index 是count的下标。
for(i=1;i<=p[0];i++){
//从第i个开始，统计其组成的最大有序数个数。
index = 0;
count[index] = i;//初始化
//首先查找出一组有序数列，并记录其下标在count中。
for(j=i+1;j<=p[0];j++){
if(p[count[index]] < p[j]){
count[++index] = j;
}
}
//判断这组数列的个数是否比已经记录的大。
if(max < (index+1)){
max = index + 1;
}
//其次，删除这组有序数列的最后一个 ,再重新查找新的有序数列
//删除到count的第一个值，即index = 0为止。对于p[i]开始的统计结束。
while(index > 0){
index--;
//重新查找数列
for(j=count[index+1]+1;j<=p[0];j++){
if(p[count[index]] < p[j]){
count[++index] = j;
}
}
//统计数列的个数
if(max < (index+1)){
max = index + 1;
}
}
}
return max;
}
void makeDataForDebug(int **p){
//调试用数据。
int i,j;
int data[][16]={
{
6,2,4,3,5,6,1,0,0,0,0
},
{
10,10,5,6,1,4,7,8,2,3,9
},
{
10,10,5,6,1,4,8,7,2,3,9
},
{
15,6,4,3,7,8,2,1,9,10,12,13,14,11,5,15
},
{
8,8,7,6,5,4,3,2,1
},
{
9,1,2,3,4,5,6,7,8,9
}
};
allTest = sizeof(data)/sizeof(data[0]);
for(i=0;i<allTest;i++){
p[i] = malloc((data[i][0]+1) * sizeof(int));
for(j=0;j<=data[i][0];j++){
p[i][j] = data[i][j];
}
}
}
int main(){
int *p[10];
int i;
if(debug){
makeDataForDebug(p);
printAll(p);
} else {
input(p);
}
for(i=0;i<allTest;i++){
printf("%d\n", p[i][0] - maxSorted(p[i]));
}
return 0;
}
--
2022-12-05 广告
