P13133 Trouble Sort - Solution

Problem Statement

给定一个整数序列

V

，现在对

V

中的每一组

V_i

和

V_{i+2}

进行排序操作，其中

i\in [1,n-2]

。

问按照这个方式排序出来的序列是否有序，如果无序，求出第一个错误的下标

i

。

Analysis

不难发现，这样的排序方法其实就是分别将奇数下标的元素排序，偶数下标的元素排序，我们只需要判断是否会产生冲突就可以了。

Approach

读入时直接分别加入到

odd

和

even

两个数组，分别排序，然后再合并到同一个数组中。要考虑

N

的奇偶性，注意细节。然后判断这是否是一个顺序正确的序列即可。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int n,t;
int main(){
	cin>>t;
	for(int cs=1;cs<=t;cs++){
		vector<int> a,b; 
		cin>>n;
		a.push_back(-1); //用于占位 
		b.push_back(-1);
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			if(i%2) a.push_back(x); //奇数下标给 a 
			else b.push_back(x); //偶数下标给 b 
		}
		sort(a.begin(),a.end()); //分别排序 
		sort(b.begin(),b.end());
		vector<int> c;
		for(int i=1;i<=n/2;i++){ //合并操作 
			c.push_back(a[i]);
			c.push_back(b[i]);
		}
		if(n%2) c.push_back(a[n/2+1]); //剩下一个手动加入 
		
		printf("Case #%d: ",cs);
		bool fl=0;
		for(int i=0;i<c.size()-1;i++){
			if(c[i]>c[i+1]){ //发现错误 
				cout<<i<<endl;
				fl=1;
				break;
			}
		}
		if(!fl)
			puts("OK");
	}
	return 0;
}

题解：P13133 [GCJ 2018 Qualification] Trouble Sort

文章操作

P13133 Trouble Sort - Solution

Problem Statement

Analysis

Approach

Code

相关推荐

评论

题解：P13133 [GCJ 2018 Qualification] Trouble Sort