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

113 阅读 0 评论 75 点赞

我是靠谱客的博主土豪学姐，这篇文章主要介绍Codeforces Round #744 (Div. 3) (Shifting Sort)，现在分享给大家，希望可以做个参考。

题目给你一个数组（让你排序，并且排序的次数不能能超过他给你的n次数）

写法就是拿一个已经排好的和没有排好的这样就能计算最少的次数

复制代码

#include"bits/stdc++.h"
 
using namespace std;
const int N = 55;
int s[N],v[N];
int t,n;
int main()
{
	cin >> t;
	while(t--)
	{
		memset(s,0,sizeof s);        //  一个原有的  一个排过序的
		memset(v,0,sizeof v);        
		cin >> n;
		for(int i=1 ; i<=n ;i ++){
			cin >> s[i];
			v[i] = s[i];
		}	
		sort(v+1,v+1+n);
		
		int ans = 0;
		vector<int>ve;
	 	for(int i=1 ;i <=n ; i++){
	 		if(v[i] != s[i]){
	 			ans++;
	 			int p ;                
	 			vector<int>lp;        // 存储每次排序好的位置  给原有的数组更新
	 			for(int j=i;j<=n;j++){
	 				if(v[i] == s[j]){
	 					p=j;
					 	ve.push_back(i);
	 					ve.push_back(j);
	 					ve.push_back(j-i);
	 					break;
					}else{
					 	lp.push_back(s[j]);
					}
				}                            
				int bns = lp.size();           
				s[i] = lp[bns-1];
				int cntl=0;
				for(int j=i+1;j<=p;j++){
					s[j] = lp[cntl++];
				}
			}
		}
	 	cout << ans << endl;
	 	int lo = 0;
		for(int i = 0 ; i < ve.size() ; i++){
	 		cout << ve[i] << " ";
	 		lo++;
	 		if(lo%3==0) cout << endl;
		}
	}
	
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include"bits/stdc++.h"
 
using namespace std;
const int N = 55;
int s[N],v[N];
int t,n;
int main()
{
	cin >> t;
	while(t--)
	{
		memset(s,0,sizeof s);        //  一个原有的  一个排过序的
		memset(v,0,sizeof v);        
		cin >> n;
		for(int i=1 ; i<=n ;i ++){
			cin >> s[i];
			v[i] = s[i];
		}	
		sort(v+1,v+1+n);
		
		int ans = 0;
		vector<int>ve;
	 	for(int i=1 ;i <=n ; i++){
	 		if(v[i] != s[i]){
	 			ans++;
	 			int p ;                
	 			vector<int>lp;        // 存储每次排序好的位置  给原有的数组更新
	 			for(int j=i;j<=n;j++){
	 				if(v[i] == s[j]){
	 					p=j;
					 	ve.push_back(i);
	 					ve.push_back(j);
	 					ve.push_back(j-i);
	 					break;
					}else{
					 	lp.push_back(s[j]);
					}
				}                            
				int bns = lp.size();           
				s[i] = lp[bns-1];
				int cntl=0;
				for(int j=i+1;j<=p;j++){
					s[j] = lp[cntl++];
				}
			}
		}
	 	cout << ans << endl;
	 	int lo = 0;
		for(int i = 0 ; i < ve.size() ; i++){
	 		cout << ve[i] << " ";
	 		lo++;
	 		if(lo%3==0) cout << endl;
		}
	}
	
	
	return 0;
}