[853] Car Fleet

是一個轉過來又轉過去的題目

沒看解答的話完全推導不出XD (大笑）

說是要先把每台車的起點sorting，（此時要綁定每台車的速度)，

再來算出每台車的抵達時間，將抵達時間拿去做monotonic stack

因為要花最久時間抵達的想必是永遠追不上別人，

所以利用到monotonic stack的精神，若進來的人比較大，把比它小的人都pop掉，

不中用不需要留～（誤)

而當有一台比較快的車追上比較慢的車之後，他們都會用同樣的比較慢的速度再繼續前進

所以monotonic stack完美利用～～～最後就是回傳剩下的stack size. 

另外要注意的是抵達時間要改用float，以免 1.xxx 跟1.0 其實是表市1.xxx沒有追上1.0

再來呢，看到別人把抵達時間也放進structure裡，好像很精簡，

但看起來整組送去qsort compare的時候 雖然只比第一個int，

彷彿好像貌似可能會因為structure 比較大(?) 而整組變慢，快不了。

所以這裡還是貼個比較冗長但是比較快的版本！

最後的最後XD 抵達時間不需要另外用一個array存

在stack的時候用個tmp float 去算＆就可以了～～～～以上。

struct CARS {

int position;

int speed;

// float sec;

};

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

struct CARS tmpA= *(struct CARS*)a;

struct CARS tmpB= *(struct CARS*)b;

return (tmpA.position- tmpB.position);

}

int carFleet(int target, int* position, int positionSize, int* speed, int speedSize) {

struct CARS *group = calloc (positionSize, sizeof ( struct CARS ));

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

{

group[i].position = position[i];

group[i].speed = speed[i];

}

qsort((void *)group, positionSize , sizeof(struct CARS ), comp);

int top = -1;

float *stack = calloc(positionSize, sizeof(float));

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

{

float tmp = (float)(target-group[i].position)/group[i].speed;

while (top >=0 && tmp>= stack[top])

top--;

stack[++top]= tmp;

}

return top+1;

}