林希是個購物狂。每次只要有買二送一的折扣,她就像瘋了一樣要買下店裡所有的商品。你已經放棄治療她的病了,但是想減少她的支出。
你知道買二送一所送的一定是結帳商品中最便宜的那幾樣。比如說,你的朋友拿了價值為400, 350, 300, 250, 200, 150, 及 100 的七樣商品到櫃臺去結帳,她就得付 1500 元。她省下了最便宜的兩樣商品的價錢(150元及100元),也就是 250 元。如果她分三次去結帳,她可以省下更多的錢。比如說,她先拿400, 300 和 250 的去結,第一次就可以省下 250 元。第二次她只拿 150 元的去結,沒有折扣。但是第三次她拿 350, 200, 和 100 的去結,又省了 100 元,總共省下了 350 元。
你的工作便是找出林希最多可以省多少錢。
Input
輸入的第一列含有一個整數 ,代表以下有多少筆測試資料。每筆測試有兩列,第一列是林希買的商品數 1 <= n <= 20000。下一列則是這些商品的價格 1 <= pi <= 20000。請參考 Sample Input。
Output
每筆測試資料輸出一列,印出如果林希適當地分次結帳時所能省下的最大金額。
| Sample Input | Sample Output |
26400 100 200 350 300 2503100 20 25 |
40020 |
考驗 Sorting 的題目。
用 Bubble Sort 需要 7xx ms,用插入 Sort 需時 1xx ms ,上傳ACM 通通 TLE
最後找 Quicksort 來用只要 8ms 才成功 AC.
#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()
{
int Item[30000];
int Item_Num,Item_Index;
int Test_Num,Test_Index;
int i,j,k,tmp;
int Break = 0;
scanf("%d",&Test_Num);
for(Test_Index = 0;Test_Index <Test_Num;Test_Index++)
{
scanf("%d",&Item_Num);
if((Item_Num >=1) && (Item_Num <=20000))
{
for(Item_Index = 0;Item_Index <Item_Num;Item_Index++)
{
scanf("%d",&Item[Item_Index]);
}
quicksort(Item, 0, Item_Num-1, Item_Num);
tmp = 0;
for(i=0;i<Item_Num;i++)
{
if((i%3)==2)
{
tmp += Item[i];
}
}
printf("%d\n",tmp);
}
}
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);
}
}
文章標籤
全站熱搜