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

74 阅读 0 评论 49 点赞

我是靠谱客的博主和谐皮皮虾，最近开发中收集的这篇文章主要介绍Codeforces Round #744 (Div. 3) B. Shifting Sort 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接

贪心

这道题我们可以用一种贪心的思想，题目是要求我们将数组按照向左循环移动的方法使数组单调递增，那么我们可以先找到当前未排序的最大值，通过移动1个距离使最大值到其原本的位置，也就是移动该值至该值应该在的位置的那一段，拿{2，5，1，4，3}举例，我先找到未排序的最大值5，它原本的位置应该是在5，但它现在在2的位置，所以我只需要移动2至5，移动距离为1，我就可以将5放在正确的位置，此时数组变成了{2，1，4，3，5}然后再接着找未排序的最大值，也就是4，它在3，所以移动3至4，距离为1，数组变为{2，1，3，4，5}，依次类推···

代码

#include<iostream>
#include<algorithm>
#include<queue> 
using namespace std;
typedef pair<int,int>PII;
int a[60],b[60];

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		queue<PII> q;
		cin>>n;
		int res=0;
		for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
		sort(b+1,b+1+n);//设置一个正确顺序的对照数组 
		for(int i=n;i>1;i--)//从最高位开始 
		{
			int f=0;
			for(int j=1;j<=i;j++)
			{ 
				if(b[i]==a[j]&&i==j&&f==0)break;//如果这个数已经在正确的位置上了就跳过 
				if(b[i]==a[j]&&f==0)
				{
					res++;
					f=1;
					q.push({j,i});
				}
				if(f)
				{
					a[j]=a[j+1];//后面的数往前移一位 
				}
			}
		}
		cout<<res<<endl;
		while(q.size())
		{
			auto t=q.front();
			cout<<t.first<<" "<<t.second<<" ";
			cout<<"1"<<endl;;
			q.pop();
		}
	}
	return 0;
}