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.

                    本来是如果暴力再对比的话~~是n^2的时间~肯定会超时~那么怎么来做呢

                    其实他说这是正常的冒泡排序~~开始和真正的是不一样的~~他的样例排序顺序：：第一遍会排 2 3 1 4 5~~第二遍会排：：1 3 2 4~~第三遍会排 1 3 2~~所以发现了吗~~我们的冒泡是增大初始点~~而他是缩小终点~~所以排序一次后的其他排序不会产生影响~~

#include<iostream>
#include<algorithm>
using namespace std;
int a[100005], b[100005];
int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for (int s = 0; s < n; s++)
	{
		scanf("%d", &a[s]);
		b[s] = a[s];
	}
	if (k == 1)
	{
		printf("-1\n");
		return 0;
	}
	sort(b, b + n);
	for (int s = 0; (s + k < n); s++)
	{
		if (a[s + k] < a[s])
		{
			swap(a[s], a[s + k]);
		}
	}
	int ans = -1;
	for (int s = 0; s < n; s++)
	{
		if (a[s] != b[s])
		{
			ans = s+1;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}