Codechef Not a Triangle題解

找出一個數組中的三個數，三個數不能組成三角形。

三個數不能組成三角形的條件是：a + b < c

兩邊和小於第三邊。

這個問題屬於三個數的組合問題了。暴力法可解，但是時間效率就是O(n*n*n)了，很慢。

不過既然是組合問題就必定可以使用排序後處理的方法降低時間效率的。

這裡降低時間效率的方法是：

選一個最大的數c，然後選兩個小數a和b，其中a < b，如果符合條件，那麼兩個數中間的數必定都可以作為b符合條件a + b < c

這樣可以把時間效率降到O(n*n)。

這個規律也不好找啊。要非常認真觀察，然後總結出來。

處理一個數組，要從小到大，從大到小反復觀察，尋找其規律。

原題：http://www.codechef.com/problems/NOTATRI/

#include 
#include 
#include 
using std::sort;

class NotATriangle
{
	//細心找出其規律進行優化
	int getNotTris_3(int *A, const int n)
	{
		sort(A, A+n);
		int i = 0, j = 1, k = n-1, ans = 0;
		for ( ; k >= 2; k--)
		{
			i = 0, j = k-1;
			while (i < j)
			{
				if (A[i] + A[j] < A[k])
				{
					ans += j - i;
					i++;
				}
				else j--;
			}
		}
		return ans;
	}
public:
	NotATriangle()
	{
		int N = 0;
		while (scanf("%d", &N) && 0 != N)
		{
			int *A = (int *) malloc(sizeof(int)* N);
			for (int i = 0; i < N; i++)
			{
				scanf("%d", &A[i]);
			}
			printf("%d\n", getNotTris_3(A, N));
			free(A);
		}
	}
};

int notATriangle()
{
	NotATriangle ntir;
	return 0;
}