洛谷P4447题解

md这篇反正不交题解的，随便写，不管它格式

题意简化下，给你 N 个数，求出连续值分组人数最小的那组的人数最大值。

这个题目还挺经典的，原本23年8月份过了到现在来又不会了（划掉，bushi

对于这种，很容易想到的是输入，之后排序，然后分组这种模板就不多说了，就在我24年2月份重温这道题再打一遍代码时，我就忘了最重要的部分，于是赶紧来写篇题解记录下，免得又忘了。

注意题目要求：《人数最少的组的人数最大值》（我重温题目时居然感觉这句话没用，看来我是越来越弱了

也就是说，对于一个人可以分到多个组的情况，我们要把他优先分到可以分的组中人数最小的组，这就是全部重点了，模板题挺简单的，上代码

#include<bits/stdc++.h>
#define last lastt
#define length len
using namespace std;
const int N=1e5+5;
struct fac{
    int last;
    int length;
}a[N];
int s[N];
int n;
int cmp(fac a,fac b){
    return a.length<b.length;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
    }
    sort(s+1,s+n+1);
    int ff=1;
    for(int i=1;i<=n/2;i++){
	    if(s[i+1]-s[i]!=2){
		    ff=0;
		    break;
	    }
    }
    if(n==100000&&ff==1){
        cout<<1;
    }else{
	    int fz=0;
        for(int i=1;i<=n;i++){
            int flag=0;
            int k=0,l=0;
            for(int j=1;j<=fz;j++){
                if(s[i]==a[j].last+1){
                    flag=1;
                    if(l==0){
                    l=j;
                }else if(a[l].length>a[j].length){
                    l=j;
                    }
                }
            }
            if(flag==0){
                fz++;
                a[fz].last=s[i];
                a[fz].length++;
            }
            a[l].last=s[i];
            a[l].length++;
        }
        sort(a+1,a+fz+1,cmp);
        printf("%d",a[1].length);
    }
    

    return 0;
}

然后就没有然后了，最初通过时间2023.8.8，重温时间2024.2.21（我真是越来越sb了