P4447 分组题解

题目传递门

一、关键语句解析:

如果有小组内人数太少,就会因为时间不够而无法获得高分,于是小可可想让你给出一个合法的分组方案,满足所有人都恰好分到一个小组,使得人数最少的组人数最多,输出人数最少的组人数的最大值。
这TM是人话吗?是我语文不好??强行理解一下:
(1)每个同学都要进入到一个组中去,不能有漏下的。
(2)需要你给出唯一的一种方案,这种方案中,每个组在满足条件的情况下尽可能的大,比如有(A,B,C,D)四组,(D)组人数最少的话,那么就输出最后(D)组的人数。说白了,就是记录此方案下,每个小组的人数最小值。
(3)啥样的条件呢?必须能力值连续;同时,不能有能力值一样的在同一组。

二、解题思路:

1、从小到大排序。
2、使用一个桶来记录每一个同学是否已经成功分配到某个组中了。
3、贪心策略为:找到一个需要分组的同学,就使劲让他所在的组最长,最长。能到(5),别到(4)。就是,以他的能力值(a[i])为基准,向后找未分组的其它同学,看看是不是存在能力值比他大(1)的人,如果存在,就变换能力值为新找到的这个人的能力值,也就是(a[i]+1)为基准,再继续向后找,以此类推,直到找完所有同学。
4、步骤3可以增加一点点优化的策略,就是,如果找到的下一个,不是和自己相等的能力值,也不是大(1)个,而是大了(2)个,(3)个,...,那么就不用继续了,因为,断线了,没有必要继续了,需要停止,就是(break)。断了的时候,就是一个非常重要的时间点,因为这时说明小组的查找结束了,以(i)号同学为首的小组找完了,我们需要记录它的长度是否为最小长度了!

  MIN = min(MIN, j - i); //完成本次分组,看看长度是多少

三、完整代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N];            //存储人员能力值
bool b[N];           //桶,用来记录是否使用过
int MIN = 0x3f3f3f3f;//组中最少人数值
int n;

int main() {
    cin >> n;
    //输入实力值并排序
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);//贪心算法,都是排序,从小到大

    //遍历每个学生
    for (int i = 1; i <= n; i++) {
        if (!b[i]) {           //此学生没有加入到组中
            b[i] = true;       //准备把他加入到某个组中

            int c = a[i];
            //对于当前学生的后面每个学生
            for (int j = i + 1; j <= n + 1; j++) {      //只有n+1这么写,最后一个才能加进来,执行这个循环
                if (!b[j]) {   //如果此人没有加入到组中
                    if (a[j] - c != 1 && a[j] != c) {   //与前一个差不是1,而且与前端的也不一样,这时,表示前面的分组就已经结束了,需要画句号了
                        MIN = min(MIN, j - i); //完成本次分组,看看长度是多少
                        break;                 //本次结束
                    } else if (a[j] - c == 1) {
                        c = a[j];               //持续本次分组中
                        b[j] = true;            //标识
                    }
                }
            }
        }
    }
    //输出大吉
    cout << MIN << endl;
    return 0;
}

四、为什么(j)的范围是到(n+1)?

比如,我们讨论一下(i=n),也就是最后一个的场景下,那么这段循环

  for (int j = i + 1; j <= n + 1; j++) { 
  }

就变成了

  for (int j = n + 1; j <= n + 1; j++) { 
  }

它会执行一次,完成小组的最终划分和小组最短长度的标记。如果范围是到(n),而不是(n+1),那就惨了:

  for (int j = n + 1; j <= n ; j++) { 
  }

直接这句就不执行了,以(n)开头的小组就会被遗忘掉,惨!

原文地址:https://www.cnblogs.com/littlehb/p/15038105.html