实力分组问题-贪心算法

Question

题目：

代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    int zu_final=0;
    int zu_now=1;
    sort(a.begin(),a.end());
    for(int i=1;i<a.size();i++)
    {
        if(a[i]-a[i-1]==0)
        {
            int k=a[i];
            a.erase(a.begin()+i);
            a.push_back(k);
            i--;
            //for(int i=0;i<n;i++)cout<<a[i]<<' ';cout<<endl;
        }
        else if(a[i]-a[i-1]==1)
        {
            zu_now++;
        }
        else
        {
            if(zu_final==0)zu_final=zu_now;
            if(zu_final!=0)zu_final=zu_final<zu_now?zu_final:zu_now;
            zu_now=1;
        }
    }
    if(zu_final==0)zu_final=zu_now;
    if(zu_final!=0)zu_final=zu_final<zu_now?zu_final:zu_now;
    //for(int i=0;i<n;i++)cout<<a[i]<<' ';
    cout<<zu_final;
    return 0;
}

思路：
先排序 -> 这样才能是连续的
重复的移动到最后面 -> 因为题目要求组不能重复实力
从头的遍历，值与前一个一样，就放到最后；值比前面大一，连续的计数++；其他的那么就是不连续的，重新计数，并比较大小更新数值。
结果：

我也不知道为么会错误
试验：

我自己试了一些例子，都是正确的呀，希望能够得到大家的帮助，谢谢大家！

Answer 1

因为你这种排序方式实质上是“让人数最多的小组人数尽可能多”，而不是“让人数最少的小组人数尽可能多”，可以参考例子“1 2 3 4 4 5 6 7 ”，这组数据应该分成“1234”“4567”两个小组最佳，而你的代码更倾向于分成“1234567”“4”

所以应该考虑如下思路：对数组进行排序。针对每个数字，若与上一个数字不相邻，则之前的小组均结算；若与上一个数字相邻，则考虑个数，若个数比当前小组数量多，则必然要组成新的小组，若比当前小组数量少，则必然有小组不能在增加人员（因为要保证最小小组的人最多，因此此时应结算人数较多的小组）。

参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,temp,prev=0;        //prev其实可以用start.size()代替
    cin >> n;
    int ans = n;
    std::vector<int> a(n);
    std::queue<int> start;
    for (int i=0; i < n; i++) cin >> a[i];
    sort(a.begin(),a.end());
    for (int i=0; i < n; ) {
        temp = 1;
        if (i == 0 || a[i]-1 != a[i-1]) {            //当前值与上一个值不相邻，则目前所有小组均不能与之后的成员组合，因此结算所有小组
            prev=0;
            while (!start.empty()) {
                ans = min(ans,a[i-1] - start.front() + 1);    //更新最小小组的人数
                start.pop();                //队列弹出小组组长，意为该小组结算完毕
            }
        }
        for (i++;i < n; i++) {
            if (a[i] == a[i-1]) temp++;
            else break;
        }for (; prev < temp; prev++) start.push(a[i-1]);    //当前值的人数比小组多，则需要成立新的小组
        for (; prev > temp; prev--) {                //当前值的人数比小组少，则结算一些小组
            ans = min(ans,a[i-1] - start.front() + 1);
            start.pop();                //为保证最小小组人数最多，先结算人数较多的小组，以使得人数较少的小组有机会继续增加人数
            //即先成立的小组先结算
        }
    }
    while (!start.empty()) {            //防止仍存在小组未结算，清空小组队列
        ans = min(ans,a[n-1] - start.front() + 1);
        start.pop();
    }
    cout << ans << endl;
}

其中start用于记录当前计算中小组的组长（每个组的首位成员），因为结算时优先选择最长的小组结算，而最长的小组必定是最早成立的小组，符合先进先出策略，故选用队列。

若仍未能解决问题，可再联系。