Minimize the Permutation(未改)_you are given a permutation of length nn. recall t-CSDN博客

本文链接：https://blog.csdn.net/Cloud_yan/article/details/103002814

这篇博客探讨了如何最小化排列过程中的错误，分析了在未知错误源的情况下解决排列问题的策略。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

自始至终，我都不知道哪里错了。

#include<stdio.h>
#include<string.h>

int a[105];
int index[105];
int index_new[105];
int main()
{
	int q;
	scanf("%d",&q);
	
	for (int i1 = 1; i1 <= q; i1++)
	{
		int length;
		scanf("%d", &length);		
		for (int i = 1; i <= length; i++)
		{
			scanf("%d", &a[i]);	//输入序列
			index[a[i]] = i;	//标记每一个数多对应的位置
		}

		int max = 1;	//在max之前的，都是排好了的，max之后的都是需要看看需不需要改变的
		memcpy(index_new, index, sizeof(int)*(length + 1));

		for (int i = 1; i <= length; i++)	//先把1排到最前面，然后2最多排到1原本的位置
		{
			if (index_new[i] == i)	//如果1···本来就排到了恰当的位置，就continue
			{
				max = i;	//max为这个恰当的位置后面的一个位置。保证不会改变这个恰当位置以及之前的了
				max++;
				continue;
			}
			if (index[i] > max)	//这里，是看这个位置是不是在max之后，max之前的已经排好了，不需要交换，只考虑max之后的
			{
				
				for (int j = index[i]; j > max; j--)	//就是交换
				{
					if (a[j] < a[j - 1])	//这里，代表只有后面的小于前面的才交换，保证是小的在前面。不会让大的换到前面
					{
						index_new[a[j]] = j - 1;	//这里是标识交换后各个的位置，比如交换后1的位置就是index_new[1]
						index_new[a[j - 1]] = j;	//因为是交换，所以两者的位置是交换了的。为的是上面确认，这个交换后的位置是不是正好是该值恰当的位置
						int temp = a[j];
						a[j] = a[j - 1];
						a[j - 1] = temp;
					}
					else break;	//如果不是小于，那么就会把大于的和小于的交换了，所以，这里是为了排除那个情况
				}
				max = index[i];	//改变max的值，使得前面的绝对都是交换好了的
				if (max == length)	//如果max到达最后一个，标志已经排好了，直接退出就好了	
					break;
			}
		}

		/*printf("%d", a[1]);*/
		for (int i = 1; i <= length; i++)
		{
			printf("%d ", a[i]);
		}
		printf("\n");
	}
	return 0;
}