100分解法

运用贪心思想，一个组最少两个人，我们尽可能让每个组都两个人，多的人再随便分配给已有的小组即可。所以答案就是sum/2，sum为所有学员总人数。但是有可能一个学院的人过多，所有其他学院的人都都和这个学院的人一一结组后这个学院还剩下>=2个人，这种情况下答案无法到达sum/2，比如[1,100]，只能结成一个小组。所以要在sum-最大值和sum/2中取一个min即为我们要的答案。

解法一：时间复杂度o(nlogn),空间复杂度o(1)。

class Solution {
public:
    /**
     * 返回最多能结成多少个学习小组
     * @param arr int整型vector 
     * @return long长整型
     */
    long long numberofgroup(vector<int>& arr) {
        // write code here
        int n=arr.size();
        sort(arr.begin(),arr.end());
        long long sum=0;
        for(int i=0;i<n-1;i++)
        {
            sum+=arr[i];
        }
        sum=min(sum,(arr[n-1]+sum)/2);
        return sum;
    }
};

解法二：时间复杂度o(n),空间复杂度o(1)。

class Solution {
public:
    /**
     * 返回最多能结成多少个学习小组
     * @param arr int整型vector 
     * @return long长整型
     */
    long long numberofgroup(vector<int>& arr) {
        // write code here
        int n=arr.size();
        long long maxn=0;
        long long sum=0;
        for(int i=0;i<n;i++)
        {
            maxn=max(maxn,(long long)arr[i]);
            sum+=arr[i];
        }
        sum=min(sum-maxn,sum/2);
        return sum;
    }
};