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

75 阅读 0 评论 50 点赞

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

概述

链接：Problem - B - Codeforces

题意：你可以选择一个区间然后把这段区间循环左移，题目要求你把这段数组从小到大排列；然后输出几步，然后输出每部的方法：l, r, d:l表示左端点， r表示右端点， d表示左移的数量；d 》= 1 && 《= r - l；次数不要求最小但是不能大于数组数量

思路：记录数组的值和初始位置，然后按照值大小从小到大排列；然后遍历数组，把排序后的位置到初始位置之间的数都左移r-l

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

struct node{
	int num;
	int i;
}arr[55], s[55];

struct edge{
	int l;
	int r;
	int d;
};

bool cmp(node a, node b){
	if(a.num == b.num){
		return a.i < b.i;
	}
	return a.num < b.num;
}

int main(){
	int t;
	int n;
	cin >> t;
	while(t--){
		cin >> n;
		for(int i = 1; i <= n; i++){
			cin >> arr[i].num;
			s[i].num = arr[i].num;
			arr[i].i = i;
			s[i].i = i;
		}
		bool flag = 0;
		for(int i = 1; i < n; i++){
			if(arr[i].num > arr[i + 1].num){
				flag = 1;
				break;
			}
		}
		if(!flag){
			cout << 0 << endl;
			cout << endl;
			continue;
		}
		int le = 0;
		int r = 0;
		sort(s + 1, s + n + 1, cmp);
		vector<edge> ve;
		for(int i = 1; i <= n; i++){
			if(i == s[i].i){
				continue;
			}
			int le = i;
			int r = s[i].i;
			ve.push_back({le, r, r - le});
			for(int l = i + 1; l <= n; l++){
				if(s[l].i >= le && s[l].i < r){
					s[l].i -= (r - le);
					if(s[l].i < le){
						s[l].i = r + 1 - (le - s[l].i);
					}
				}else if(s[l].i == r){
					s[l].i = i;
				}
			}
		}
		cout << ve.size() << endl;
		for(int i = 0; i < ve.size(); i++){
			edge ans = ve[i];
			cout << ans.l << " " << ans.r << " " << ans.d << endl;
		}
	}
	
	return 0;
}