Codeforces Round #744 (Div. 3) B. Shifting Sort

题目链接

一道模拟题，题意是给一个长度n的数组，用n次以下选定一个区域集体左移的操作把它排序成一个非递减的数组。

刚开始用冒泡写，结果下标和验重都出了问题，比赛直接寄了。之后换选择思路，还是在验重和不用排的情况出事，改了下结构才好。

#include<bits/stdc++.h>
using namespace std;

#define N 60

int a[N],ans[N];//原数组和目标数组
int l[N],r[N],d[N];//三个输出值

int main()
{
 int t;
	cin>>t;

	while(t--)
	{
		int n,i,j;
		cin>>n;
		for(i=1;i<=n;i++)
		{
			cin>>a[i];
			ans[i]=a[i];
		}

		sort(ans+1,ans+1+n);//排序构造目标数组

		int cnt=0;//需要操作的数量
		for(i=1;i<n;i++)//i指针遍历目标数组，将原数组中的ans[i]数移动到正确的位置
		{
			for(j=i;j<=n;j++)//选择排序从前到后固定，遍历下标从u
	 		{
				if(a[j]==ans[i])//找到数了
				{
					for(int k=j;k>i;k--)//操作原序列
					a[k]=a[k-1];
					break;
				}
	 		}
   			if(j!=i)//如果元素不在正确的位置
   			//这个还真不能写到里面
   			{
				l[cnt]=i,r[cnt]=j,d[cnt]=j-i;
				cnt++;
   			}
		}

		cout<<cnt<<endl;
		for(i=0;i<cnt;i++)
		cout<<l[i]<<' '<<r[i]<<' '<<d[i]<<endl;
	}
	
	return 0;
}

最后

以上就是妩媚砖头最近收集整理的关于Codeforces Round #744 (Div. 3) B. Shifting Sort的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。