사전 정렬

Sort 를 사용하여 정렬하기만 하면 됩니다 ... 당신의 정렬이 큰 것부터 작은 것까지 되었는지 확인하십시오.

그런 다음 주 알고리즘을 살펴보십시오. 너의 알고리즘은 O (N 3) 이다. N= 100000 인 데이터의 경우 심각한 시간 초과여야 합니다.

N= 100000 인 데이터의 경우 O(nlogn) 아래의 알고리즘을 사용하여 해결해야 합니다. 이 문제는 탐욕이지 수색이 아니다.

생각을 이야기하다.

가장 큰 것부터 가장 작은 것까지 정렬한 다음 가장 큰 세 면을 취하여 삼각형의 조건을 판단합니다. 그렇지 않다면, 두 번째, 세 번째, 네 번째 측면으로 판단하십시오. 그렇지 않다면, 세 번째, 네 번째, 다섯 번째 면으로 판단한다. 언제 가능할까요? 삼변의 합이 최대 둘레다.

증명:

제가 배열 a[0...n- 1] 을 가지고 있다고 가정해 봅시다. 가장 큰 세 변의 경우, 당신이 말했듯이, 여기서 삼각형을 판단하는 유일한 조건은 A [0] 입니다.