题解 P4447 【[AHOI2018初中组]分组】

I_FUCK_CM · 2018-04-17 23:25:34 · 题解

首先说60/40做法

：输入上有最少组人数最多

毅然决然二分答案

然后。。。60

好了

现在是满分做法

二分答案的同时

开N个桶

全部装进去

嗯，没错

此处给出60分代码，实在懒就对着改吧

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
int n,m,ans,ask,a[100086];
int l=1,r=100000;
int check(int x){
    int cnt=1;
    for(int i=2;i<=n+1;i++){
      if(a[i]==a[i-1]+1){
        cnt++;
      }
      else
      { 
        if(a[i]!=a[i-1]+1){
          if(cnt>=x)
            cnt=1;
         else
            return false;
        }
    }
}    

  return true;
}
int main(){
    //freopen("division.in","r",stdin);
    //freopen("division.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]);
    a[n+1]=2147483647;
    sort(a+1,a+1+n);
   while(l<=r){
    //printf("%d %d\n",l,r);
    int mid=(l+r)/2;
    if(check(mid)){
      ans=mid;
      l=mid+1;
    }
    else
    r=mid-1;
}
  printf("%d\n",ans); 
  return 0;
}