题干：

某班有 nn 个同学，每个同学有一个外向程度 a_iai​。由于要进行某个活动，需要把他们分成若干个小组，每个小组的人数至少为 mm 人。不同外向程度的人在一个小组会产生不开心值，定义一个小组的不开心值为组内成员外向程度最大值和最小值的差，一个班级的不开心值为所有小组不开心值的最大值。

那么问题来了，如何分组使得班级的不开心值最小，请你求出这个最小的班级不开心值。

输入格式

第一行两个整数 n,mn,m，分别表示人数和每个小组最少的人数要求。

第二行 nn 个整数 a_iai​，表示每个同学的外向程度。

输出格式

一个整数，表示最小的班级不开心值。

数据范围

对于 30\%30% 的数据：1\le m \le n \le 201≤m≤n≤20，1\le a_i \le 1001≤ai​≤100。

对于 60\%60% 的数据：1\le m \le n\le 10001≤m≤n≤1000，1\le a_i \le 10001≤ai​≤1000。

对于 100\%100% 的数据：1\le m\le n \le 5\cdot10^51≤m≤n≤5⋅105，1\le a_i \le 10^91≤ai​≤109。

样例解释

第一个样例，只要每个人各自一个组，不开心值就都是 00。

第二个样例，最佳的分组情况为：9,119,11 一个组，6,3,56,3,5 一个组，两个组的不开心值分别为 22 和 33，那么班级的不开心值为 33。

样例输入1复制

5 1
2 4 6 8 10

样例输出1复制

0

样例输入2复制

5 2
9 11 6 3 5

样例输出2复制

3

解题报告：

这题关键在于怎么check。我们用dp[i]代表：对前i个人进行划分，最后一个可以进行分组的（可以被塞进某个分组的）人的编号。

考虑最后一个人，判断当前第i个人能不能作为当前分组的最后一个人，这就需要找之前分完组后第一个没组可归的人的编号 即dp[i-m]+1。如果能作为最后一个人，那dp[i]=i,否则就是dp[i-1]。

 

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 6e5 + 5;
int n, m;
int a[MAX], dp[MAX];
bool ok(int x) {
	// dp[0~m-1]=0
	for (int i = m; i <= n; i++) {
		if (a[i] - a[dp[i - m] + 1] <= x) dp[i] = i;
		else dp[i] = dp[i - 1];
	}
	return dp[n] == n;
}
int main() 
{
	cin>>n>>m;
	for (int i = 1; i <= n; i++) scanf("%d", a+i);
	sort(a + 1, a + n + 1);
	int l = 0, r = 1e9;
	int mid = (l + r) >> 1;
	while (l < r) {
		mid = (l + r) >> 1;
		if (ok(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}

另一个dp做法：

所有数据首先经过排序。 我们如果用dp[i]表示前i个数字在猜测答案x的条件下，是否能够划分成比m大的子集和。那么dp[i]可以去把l…r-1的一串数字染成true，l=i+m，r是第一个不满足a[r]-a[i+1]<=x的位置（当然r可能小于或等于l，这时候不染色）。
 每check一次dp一次，返回的是dp[n]是否为true。
 然而这样的话dp最差是n^2效率，可以想到用树状数组+扫描线或者线段树来改进。但是五十万的数据不允许两个log存在。实际上可以发现由于我们的点查询是从左到右连续的，所以没必要搞树状数组，直接扫描线就行了，然后dp[i]就是i处的覆盖区间数，也就是扫描线数组的前缀和，前缀和大于0相当于为true，否则为false。

原先做n^2的dp的话，是如果dp[i]是true的话，那么后面l~r-1也更新为true。

考虑到这个过程像是区间覆盖，所以可以用端点处+1 ，-1，然后用前缀和来表示真正的dp值（这个前缀和也就是代码里的pre，pre>0表示曾被true覆盖过，，也就是原先意义下的dp[i]=true）。。

只要i是可以达到的，l~r-1就可以从i处增加一个子集来达到。


链接

#include<cstdio>
#include<algorithm>
#include<queue>
#define M (L+R>>1)
using namespace std;

int n,a[500005],m,L,R,dp[500005];

bool check(int x)
{
	dp[0]=1;
	dp[1]=-1;
	for(int i=2;i<=n;i++)
		dp[i]=0;
	int pre=0;
	for(int i=0,j=1,l,r;i<=n;i++)
	{
		pre+=dp[i];
		if(!pre)
			continue;
		while(j<=n&&a[j]-a[i+1]<=x)
			j++;
		l=i+m;
		r=j;
		if(l>=r)
			continue;
		dp[l]++;
		dp[r]--;
	}
	return pre>0; 
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	L=0;
	R=a[n]-a[1];
	while(L<R)
		if(check(M))
			R=M;
		else
			L=M+1;
	printf("%d",L);	
	return 0;
}