Leetcode1561. 你可以获得的最大硬币数目

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;
}

结果:
Leetcode1561. 你可以获得的最大硬币数目

关于qsort

qsort函数是C语言编译器函数库自带的排序函数。

详情请见:qsort() | 菜鸟教程

上一篇:DBHelper


下一篇:qsort函数的模拟实现