前言

这是Google的第二题，这题跟上一题比起来简易了许多，主要使用排序功能。
我国文造诣真的很差，打篇文章都笔写程式还久了有点惨...请见谅。
原题目

题目

Code Jam仔细研究了经典的泡沫排序法，然而发现了一个新的变种。
正常的泡沫排序法是检查相邻的数字，如果左边大于现在的数字，则交换。但是我们的算法是三个相邻的数字，如果左边数字大于右边数字，则翻转整组，因此我们将"三个一组泡沫排序"命名为Trouble Sort。
例如，L = 5 6 6 4 3，Trouble Sort排序如下:

第一关:检查5 6 6，无动作: 5 6 6 4 3检查6 6 4，6 > 4，反转: 5 4 6 6 3检查6 6 3，6 > 3，反转: 5 4 3 6 6第二关:检查5 4 3，5 > 3，反转: 3 4 5 6 6检查4 5 6，无动作: 3 4 5 6 6检查5 6 6，无动作: 3 4 5 6 6第三遍检查，因为都无动作所以结束。
我们期待在夏威夷上的排绿会议展示Trouble Sort，但我们实习生指出了一个问题：Trouble Sort可能没有正确排序！例如，8 9 7。
我们需要您的帮助进一步研究。给N个整数列表，确认Trouble Sort是否能成功将列表中的整数排序为非递减排序。如果不能，则找到第一格排序错误的索引(从0开始):就是第一个值大于前面的值。

输入

输入的第一行T测试笔数。每个测试笔数有两行组成：一行整数N，列表中的大小，然后另一行带有个N个整数V。

输出

输出每笔资料，包含Case #x: y，其中x是测试笔数编号，如果是正确排序y输出OK，如果不是则输出第一个错误的索引（从0开始）。

範围

1 <= Ť <= 100 。
1 <= V <= pow(10,9)。
测资1: 3 <= N <=100 每个测试集10秒。
测资2: 3 <= N <= pow(10,5) 每个测试集20秒。
记忆体限制：1GB。

範例

输入:
2
5
5 6 8 4 3
3
8 9 7

输出:
Case #1: OK
Case #2: 1

解析

由上述範例可知道我们比较都是隔一个来比较，而大于右边则翻转，翻转其实是最左最右交换。奇数索引不会影响到偶数索引则可分为2个数列，奇数索引数列和偶数索引数列，将其排序。排序后将两组合併放回原本的位置上，即可得到答案。

程式码

做了STL版本和指标版本，测试看Google测资输出会不会有问题，很幸运的Google的都可以使用。
1.STL版本

#include <iostream>#include <vector>#include <algorithm>#include "math.h"using namespace std;// 输出void Print(const int& index, const int& result){if (result == -1){cout << "Case #" << index + 1 << ": OK" << endl;}else{cout << "Case #" << index + 1 << ": " << result << endl;}}// num1: 奇数数列// num1: 偶数数列int Compute(vector<int>& num1, vector<int>& num2){    // 直接对奇数和偶数排序，可换成自己实作排序(O(N^2)应该是不能)。sort(num1.begin(), num1.end());sort(num2.begin(), num2.end());int nowNum = num1[0];        // 检查奇数索引和偶数索引两个相邻，是否是非递减，若不是则回传索引位置。    // 依照num2的大小来取得索引, 所以要乘上2才是原本索引位置。    // 为何回传上一个索引位置? 因我们是用上一个数字来比较，反之用下一个比较则传回当下索引for (size_t index = 0; index < num2.size(); index++){if (nowNum > num1[index]){return (index << 1) - 1;}if (num1[index] > num2[index]){return (index << 1);}nowNum = num2[index];}    // num1可能会比num2多一个数字，若小于上一个数字则回传上一个索引位置。    // 索引位置num1大小乘上2 - 2为最大索引(因为num2少1所以要多减1)，回传上一个，所以减3if (num1.size() > num2.size()&& nowNum > num1[num1.size() - 1]){return (num1.size() << 1) - 3;}return -1;}// 输入void Input(){    //笔数int testCount = 0;    while (cin >> testCount){for (int count = 0; count < testCount; count++){            // 数列长度int numSize;cin >> numSize;vector<int> num1(static_cast<unsigned int>(ceil(numSize / 2.0)));vector<int> num2(static_cast<unsigned int>(floor(numSize / 2.0)));                        // 输入奇偶数列for (size_t index = 0; index < num2.size(); index++){cin >> num1[index] >> num2[index];}                        // 奇数可能多一个if (num1.size() > num2.size()){cin >> num1[num1.size() - 1];}int result = Compute(num1, num2);Print(count, result);}}}int main(){Input();return 0;}

2.指标版本

#include <iostream>#include <algorithm>#include "math.h"using namespace std;// 输出void Print(const int& index, const int& result){if (result == -1){cout << "Case #" << index + 1 << ": OK" << endl;}else{cout << "Case #" << index + 1 << ": " << result << endl;}}// num1: 奇数数列// num1: 偶数数列// num1Size: num1大小// num2Size: num2大小int Compute(int*& num1, int*& num2, unsigned int num1Size, unsigned int num2Size){    // 直接对奇数和偶数排序，可换成自己实作排序(O(N^2)应该是不能)。sort(num1, num1 + num1Size);sort(num2, num2 + num2Size);int nowNum = num1[0];        // 检查奇数索引和偶数索引两个相邻，是否是非递减，若不是则回传索引位置。    // 依照num2的大小来取得索引, 所以要乘上2才是原本索引位置。    // 检查到则回传上一个索引位置，因我们是用上一个数字来比较，反之用下一个比较则传回当下索引for (unsigned int index = 0; index < num2Size; index++){if (nowNum > num1[index]){return (index << 1) - 1;}if (num1[index] > num2[index]){return (index << 1);}nowNum = num2[index];}    // num1可能会比num2多一个数字，若小于上一个数字则回传上一个索引位置。    // 索引位置num1大小乘上2 - 2为最大索引(因为num2少1所以要多减1)，回传上一个，所以减3if (num1Size > num2Size&& nowNum > num1[num1Size - 1]){return (num1Size << 1) - 3;}return -1;}// 删除指标template <class T>inline void DeleteArray(T& ptr){delete[] ptr;ptr = nullptr;}// 输入void Input(){    //笔数int testCount = 0;    while (cin >> testCount){for (int count = 0; count < testCount; count++){            // 数列长度int numSize;cin >> numSize;            unsigned int num1Size = static_cast<unsigned int>(ceil(numSize / 2.0));unsigned int num2Size = static_cast<unsigned int>(floor(numSize / 2.0));int* num1 = new int[num1Size];int* num2 = new int[num2Size];                        // 输入奇偶数列for (unsigned int index = 0; index < num2Size; index++){cin >> num1[index] >> num2[index];}                        // 奇数可能多一个if (num1Size > num2Size){cin >> num1[num2Size - 1];}int result = Compute(num1, num2);                        DeleteArray(num1);DeleteArray(num2);            Print(count, result);}}}int main(){Input();return 0;}

结果

以上两个版本看起来其实大同小异，对于我来说指标版本方便在可以控制神么时候要释放记忆体，这里在result后就释放掉记忆体了，vector部分则要等到Print跑完，如果认知有误或还有更好算法希望大大们指导提供。