前言

這是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

解析

1. 由上述範例可知道我們比較都是隔一個來比較，而大於右邊則翻轉，翻轉其實是最左最右交換。
2. 奇數索引不會影響到偶數索引則可分為2個數列，奇數索引數列和偶數索引數列，將其排序。
3. 排序後將兩組合併放回原本的位置上，即可得到答案。

程式碼

做了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)，回傳上一個，所以減3
	if (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)，回傳上一個，所以減3
	if (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跑完，如果認知有誤或還有更好算法希望大大們指導提供。