Every day a leetcode
题目来源:1561. 你可以获得的最大硬币数目
解法:贪心
每一次拿硬币,我们只能拿第二多的。
根据贪心的思想,要使我们拿到的硬币数最大。
先将硬币堆从小到大排序。
每一次分配,alice拿走最大的,我们拿走第二大的,bob拿走最小的,这样一来,剩余的硬币堆是最大的,我们能拿到的硬币数也是最多的。
代码:
int cmpfunc(const void *a, const void *b)
{
return (*(int*)a-*(int*)b);
}
int maxCoins(int* piles, int pilesSize){
int ans=0;
qsort(piles,pilesSize,sizeof(int),cmpfunc);
int count=pilesSize/3;
int index=pilesSize-2;
while(count--)
{
ans+=piles[index];
index-=2;
}
return ans;
}
结果:
关于qsort
qsort函数是C语言编译器函数库自带的排序函数。
详情请见:qsort() | 菜鸟教程