d150: 11369 - Shopaholic

內容 ：
    林希是個購物狂。每次只要有買二送一的折扣，她就像瘋了一樣要買下店裡所有的商品。你已經放棄治療她的病了，但是想減少她的支出。
    你知道買二送一所送的一定是結帳商品中最便宜的那幾樣。比如說，你的朋友拿了價值為400, 350, 300, 250, 200, 150, 及 100 的七樣商品到櫃枱去結帳，她就得付 1500 元。她省下了最便宜的兩樣商品的價錢，也就是 250 元。如果她分三次去結帳，她可以省下更多的錢。比如說，她先拿400, 300 和 250 的去結，第一次就可以省下 250 元。第二次她只拿 150 元的去結，沒有折扣。但是第三次她拿350, 200, 和 100 的去結，又省了 100 元，總共省下了 350 元。
    你的工作便是找出林希最多可以省多少錢。

輸入說明 ：
    第一行是測試筆數 1 ≤ t ≤ 20。每筆測試有兩行輸入。第一行是林希買的商品數 1 ≤ n ≤ 20000。下一行則是這些商品的價格 1 ≤ pi ≤ 20000。

輸出說明 ：
    每個測試，輸出一行，印出如果林希適當地分次結帳時所能省下的最大金額。

範例輸入 ：
1
6
400 100 200 350 300 250

範例輸出 ：
400

出處 ：
    UVa ACM 11369

程式碼 ：

#include <stdio.h> 
#include <stdlib.h> 

#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

void quicksort(int[], int, int, int); 

int main(void)
{ 
    int t,n,i,num[20000],ans;
    
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0; i<n; i++)
            scanf("%d",&num[i]);
        quicksort(num, 0, n-1, n);
        
        ans = 0;
        for(i=2; i<n; i=i+3)
            ans+=num[i];
        printf("%d\n",ans);
    }
    return 0; 
}

void quicksort(int number[], int left, int right, int MAX)
{
    int i, j, s;
    if(left < right)
    {
        s = number[left];
        i = left;
        j = right + 1;
        while(1)
        {
            while(i + 1 < MAX && number[++i] > s) ;
         
            while(j -1 > -1 && number[--j] < s) ;
            if(i >= j)
                break;
            SWAP(number[i], number[j]);
        }
        number[left] = number[j];
        number[j] = s;
        quicksort(number, left, j-1, MAX);
        quicksort(number, j+1, right, MAX);
    } 
}

http://zerojudge.tw/ShowProblem?problemid=d150