Sorting Trees

NC15803. Sorting Trees

描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.

One day the tree manager of HUST asked you to sort N trees increasing by their heights a_i. Because you were a warm-hearted and professional programmer, you immediately wrote the Bubble Sort to finish the task. However, you were so tired that made a huge mistake:

for(int i=1;i<n;i++)     for(int j=1;j<=n-i;j++)          if(a[j+k]<a[j])swap(a[j+k],a[j]);

Usually k=1 is the normal Bubble Sort. But you didn't type it correctly. When you now realize it, the trees have been replanted. In order to fix them you must find the first place that goes wrong, compared with the correctly sorted tree sequence.

If every trees are in their correct places then print -1. And you should know k can be equal to 1 which means you didn't make any mistake at all. Also you don't need to consider the part j+k beyond n.

输入描述

The first line contains two integers N and K as described above.
Then the next line are N integers indicating the unsorted trees.

输出描述

A integer in a single line, indicating the first place that goes wrong. Or -1 means no mistake.

示例1

输入:

5 2
2 3 1 4 5

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3(3.5.2) 解法, 执行用时: 318ms, 内存消耗: 31852K, 提交时间: 2018-04-29 15:46:27

n, k = map(int, input().split())
a = list(map(int, input().split()))

s = sorted(a)
p = [[j for j in range(i, len(a), k)] for i in range(k)]
b = [sorted([a[j] for j in range(i, len(a), k)]) for i in range(k)]
for i in range(len(p)):
    for j in range(len(p[i])):
        a[p[i][j]] = b[i][j]
for i in range(len(a)):
    if a[i] != s[i]:
        print( i + 1 )
        break
else:
    print( -1 )

C++11(clang++ 3.9) 解法, 执行用时: 29ms, 内存消耗: 2380K, 提交时间: 2018-05-03 21:05:21

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int a[maxn],b[maxn];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	if(k==1){
		printf("-1\n");
		return 0;
	}
	sort(b,b+n);
	int ans=-1;
	for(int i=0;i<n;++i){
		if(a[i]!=b[i]) {
			ans=i+1;
			break;
		}
	}
	printf("%d",ans);
}