575. 分糖果

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:

输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。
示例 2 :

输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。
注意:

数组的长度为[2, 10,000]，并且确定为偶数。
数组中数字的大小在范围[-100,000, 100,000]内。

class Solution {

    /**

     * @param Integer[] $candies

     * @return Integer

     */

    function distributeCandies($candies) {

        if(empty($candies)) return 0;

        $boy = array();

        $count = count($candies);

        //candies value map

        $values = array_count_values($candies);

        arsort($values);

        //弟弟能够拿到的糖果数量

        $xuNumber = $count / 2;

        //最小值

        $min = end($values);

        $sum = 0;

        foreach ($values as $key => &$value) {

            //能力最小的先不承担责任

            if($value == $min) continue;

            //暂时能承担的责任

            $diff = $value - $min;

            $value = $value - $diff;    

            $xuNumber -= $diff;

        }

        if($xuNumber == 0)  return count($values);

        //大家能力都一样了，都来承担，一层一层剥削

        while ( $xuNumber > 0) {

            foreach ($values as $key => &$t) {

                $t = $t - 1;

                if($t == 0) unset($values[$key]);

                $xuNumber = $xuNumber - 1;

                if($xuNumber == 0) break;

            }

        }

        return count($values);    

    }

}

本作品采用《CC 协议》，转载必须注明作者和本文链接