[2706] Buy Two Chocolates

散播歡樂散播愛的 easy題目

但我為什麼就是比別人慢那麼一節XD

多宣告個int來存不好嗎 XD

int comp(const void *a, const void *b)

{

return ( *(int *)a - *(int*)b );

}

int buyChoco(int* prices, int pricesSize, int money){

qsort((void*)prices, pricesSize,sizeof(int), comp);

if (money - prices[0] -prices[1]>=0)

return money - prices[0] -prices[1];

else

return money;

#if 0 // this is slow...

int ret = money;

ret = money - prices[0] -prices[1];

return (ret>=0)?(ret):(money);

#endif

}

看到有人用linear直接暴力找最小兩個值，好像也沒有不行，但好像也沒有快多少？！

這次多宣告一個又變的比較快了，應該是看系統忙不忙的概念吧 XDD

int buyChoco(int* prices, int pricesSize, int money){

int min1= INT_MAX;

int min2= INT_MAX;

for (int i=0;i<pricesSize; i++)

{

if (prices[i] < min1 && prices[i] < min2)

{

min2=min1;

min1=prices[i];

}

else if (prices[i]< min2 && prices[i]>= min1)

min2=prices[i];

}

int tmp = money - min1-min2;

if (tmp >=0)

return tmp;

else

return money;

}

最後，看到用C寫的最快的是用bubble sort先sorting，心想這沒可能啊我用qsort會比它慢嗎！！！把它貼過來仔細研究了一下，原來bubble sort裡偷藏了一個 swapped來紀錄是不是已經sorting好了，是的話就return  不做了 （？！）怎麼好像有一點偷吃步！！！但我有點懶的看是不是裡面的回圈index 也要跟著改了XD （這樣不求甚解好嗎....)

總之先貼在這裡如果有緣的話再研就好了Orz 雖然我希望最好是沒有緣啦= = +

void swap(int* xp, int* yp){
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void bubbleSort(int arr[], int n){
    int i, j;
    bool swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = false;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }

        if (swapped == false)
            break;
    }
}