题目大意：有n根长度的为a1,a2....an的棒子，如果棒子可以组成三角形，求这些棒子能组成的三角形的最大周长？
这一题，一般人只能想到三重循环，当然我们是CS专业的，不能这样想，其实这题可以用DP（其实也不算DP），就是用o(n^2)的时间算出所有两根棒子的组合，然后再n的时间从大到小匹配
其实这一题有更简单的O（nlogn）的算法，那就是，既然我们都要选周长最大的三角形，那为什么我们不能从最大的棒子开始匹配呢？这样一想，其实DP也是在做这样的事情，从最大的开始做起，那么以为棒子的输入是随机的，我们就快排一次，然后从n-2开始往下匹配，完成任务
这一题真的是很简单，但是我一开始的时候还是没有想到，看来我还是需要很多锻炼
#include <stdio.h>
#include <stdlib.h>
#define CUTOFF 20 typedef int Position;
void Quick_Sort(Position, Position, Position *);
void Swap(Position, Position,Position *);
int Median_of_Three(Position, Position, Position,Position *);
void Insertion_Sort(Position, Position, Position *);
void Search(Position *, const int); int main(void)
{
int n, i;
while (~scanf("%d", &n))
{
if (n == )
break;
Position *A = (Position *)malloc(sizeof(Position)*n);
for (i = ; i < n; i++)
scanf("%d", &A[i]);
Quick_Sort(, n - , A);
Search(A, n);
free(A);
}
return ;
} void Swap(Position x, Position y, Position *A)
{
A[x] ^= A[y];
A[y] ^= A[x];
A[x] ^= A[y];
} int Median_of_Three(Position left, Position mid , Position right,Position *A)
{
if (A[left] > A[mid])
Swap(left, mid, A);
if (A[left] > A[right])
Swap(left, right, A);
if (A[mid] > A[right])
Swap(mid, right, A);
Swap(mid, right, A);
return A[right];
} void Insertion_Sort(Position left, Position right, Position *A)
{
int i, j, tmp;
for (i = left + ; i <= right; i++)
{
tmp = A[i];
for (j = i; j > left && A[j - ] > tmp; j--)
A[j] = A[j - ];
A[j] = tmp;
}
} void Quick_Sort(Position left, Position right, Position *A)
{
Position mid = (left + right) / ;
int i = left, j = right, pivot;
if (right - left > CUTOFF)
{
pivot = Median_of_Three(left, mid, right, A);
while (i < j)
{
while (A[++i] < pivot);
while (A[--j] > pivot);
if (i < j)
Swap(i, j, A);
else break;
}
Swap(i, right, A);
Quick_Sort(left, i - , A);
Quick_Sort(i + , right, A);
}
else
Insertion_Sort(left, right, A);
} void Search(Position *A, const int n)
{
int found = , i;
for (i = n - ; i >= ; i--)
{
if (A[i] < A[i - ] + A[i - ])
{
printf("%d\n", A[i] + A[i - ] + A[i - ]);
found = ;
break;
}
}
if (!found)
printf("0\n");
}