贪心二分之分组组队

P4447 [AHOI2018初中组] 分组 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

如何使得分组后人数最小的小组的人数最多，那就是尽可能的均分，从而使得分完组后的最小组的人数最多。

该怎么做，我们的做法是首先将所有的人的实力按升序排列，拍好后，我们将实力连续的人们分为一组。一旦出现两个实力相等或者差距大于一，我们就从这个人开始再分一个组，这样就可以保持尽量的均分。举个例子，1，1，2，2，3，3，4，4分组分为两组每组四个人首先按1是第一组，继续下来又是一个1把它分为第二组，接下来是2，记住我们把它分到第二组，又是额2，把它分到的第一组。

就是这样分，一个数优先从后面的组遍历到前面的小组，如果能在后面的小组接上，就接在后面的小组上。为什么呢，我们想如果把所有的数优先接到第一组上那么1，2，3，3，4，答案就是1而不平均，而优先接到后面的组上就可以平均了。做法有了，就上代码，

dp数组代表着排好序的数字，dp2数组代表每一组以那个数字结尾，dp3数组代表着这一组的人数。我饿们使用二分找到最右边的合法小组

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {	
  public static void main(String[] args) throws NumberFormatException, IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
int a=Integer.parseInt(br.readLine());
long[] dp=new long[a];
long[] dp2=new long[a];
long[] dp3=new long[a];
Arrays.fill(dp2, Integer.MAX_VALUE);
int b;
int c;
String[] aStrings=br.readLine().split(" ");
for(b=0;b
	dp[b]=Long.parseLong(aStrings[b]);
}
Arrays.sort(dp);
c=0;
long answer=Long.MAX_VALUE;
long d=1;
dp3[0]=1;
dp2[0]=dp[0];
for(b=1;b
	if(dp[b]-dp[b-1]==1) {
		dp3[c]++;
		dp2[c]=dp[b];
	}
	else {
		int biaoji=0;
	int ff=check(dp2, 0, c,dp[b]-1 );
		if(ff>=0) {
			dp2[ff]=dp[b];
			dp3[ff]++;
			biaoji=1;
		
		}
	
	if(biaoji==0) {
		c++;
		dp2[c]=dp[b];
		dp3[c]++;
	}
		
	}
}
for(int dd=0;dd<=c;dd++) {
	answer=Math.min(answer, dp3[dd]);
}
System.out.println(answer);
	}
	public static int check(long[] a,int b,int c,long d) {
		
int e=-1;
         while(b<=c) {
        	 int mid=(b+c)>>>1;
        	 if(a[mid]==d) {
        		 e=mid;
        		 b=mid+1;
        	 }
        	 else if(a[mid]
        		 b=mid+1;
        	 }
        	 else {
				c=mid-1;
			}
         }
         return e;
	}
}