Greedy:三角形问题

　　题目大意：有n根长度的为a1,a2....an的棒子，如果棒子可以组成三角形，求这些棒子能组成的三角形的最大周长？

　　这一题，一般人只能想到三重循环，当然我们是CS专业的，不能这样想，其实这题可以用DP（其实也不算DP），就是用o(n^2)的时间算出所有两根棒子的组合，然后再n的时间从大到小匹配

　　其实这一题有更简单的O（nlogn）的算法，那就是，既然我们都要选周长最大的三角形，那为什么我们不能从最大的棒子开始匹配呢？这样一想，其实DP也是在做这样的事情，从最大的开始做起，那么以为棒子的输入是随机的，我们就快排一次，然后从n-2开始往下匹配，完成任务

　　这一题真的是很简单，但是我一开始的时候还是没有想到，看来我还是需要很多锻炼

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define CUTOFF 20
 4 
 5 typedef int Position;
 6 void Quick_Sort(Position, Position, Position *);
 7 void Swap(Position, Position,Position *);
 8 int Median_of_Three(Position, Position, Position,Position *);
 9 void Insertion_Sort(Position, Position, Position *);
10 void Search(Position *, const int);
11 
12 int main(void)
13 {
14     int n, i;
15     while (~scanf("%d", &n))
16     {
17         if (n == 0)
18             break;
19         Position *A = (Position *)malloc(sizeof(Position)*n);
20         for (i = 0; i < n; i++)
21             scanf("%d", &A[i]);
22         Quick_Sort(0, n - 1, A);
23         Search(A, n);
24         free(A);
25     }
26     return 0;
27 }
28 
29 void Swap(Position x, Position y, Position *A)
30 {
31     A[x] ^= A[y];
32     A[y] ^= A[x];
33     A[x] ^= A[y];
34 }
35 
36 int Median_of_Three(Position left, Position mid , Position right,Position *A)
37 {
38     if (A[left] > A[mid])
39         Swap(left, mid, A);
40     if (A[left] > A[right])
41         Swap(left, right, A);
42     if (A[mid] > A[right])
43         Swap(mid, right, A);
44     Swap(mid, right, A);
45     return A[right];
46 }
47 
48 void Insertion_Sort(Position left, Position right, Position *A)
49 {
50     int i, j, tmp;
51     for (i = left + 1; i <= right; i++)
52     {
53         tmp = A[i];
54         for (j = i; j > left && A[j - 1] > tmp; j--)
55             A[j] = A[j - 1];
56         A[j] = tmp;
57     }
58 }
59 
60 void Quick_Sort(Position left, Position right, Position *A)
61 {
62     Position mid = (left + right) / 2;
63     int i = left, j = right, pivot;
64     if (right - left > CUTOFF)
65     {
66         pivot = Median_of_Three(left, mid, right, A);
67         while (i < j)
68         {
69             while (A[++i] < pivot);
70             while (A[--j] > pivot);
71             if (i < j)
72                 Swap(i, j, A);
73             else break;
74         }
75         Swap(i, right, A);
76         Quick_Sort(left, i - 1, A);
77         Quick_Sort(i + 1, right, A);
78     }
79     else
80         Insertion_Sort(left, right, A);
81 }
82 
83 void Search(Position *A, const int n)
84 {
85     int found = 0, i;
86     for (i = n - 1; i >= 2; i--)
87     {
88         if (A[i] < A[i - 1] + A[i - 2])
89         {
90             printf("%d
", A[i] + A[i - 1] + A[i - 2]);
91             found = 1;
92             break;
93         }
94     }
95     if (!found)
96         printf("0
");
97 }