题目描述

给出 N N N 个数，我们需要选择其中的 R × C R×C R×C 个数,，把它们填入一个 R × C R×C R×C 的矩阵（ R R R 行 C C C 列）中。

我们先定义一个函数 D ( i ) D(i) D(i) 代表第 i i i行中最大的数和最小的数之差。对于整个矩阵，定义 F F F 为矩阵中 D ( i ) ( 1 ≤ i ≤ R ) D(i)(1≤i≤R) D(i)(1≤i≤R) 的最大值。

我们需要 F F F 的值最少，你能求出最少可能达到的 F F F 值是多少吗？

输入格式

第一行给出 3 3 3个整数 N , R , C N,R,C N,R,C，对应题目中描述的参数。

接下来一行有 N N N 个整数，代表 N N N 个可以选择的数 P i P i Pi 。

输出格式

输出一行表示最少可能达到的 F F F 值。

输入输出样例

输入 #1

7 2 3
170 205 225 190 260 225 160

输出 #1

30

分析：

二分+模拟
先排序 保证单调 然后二分
二分最大差值 看看当前最大差值<最大差值 并满足行数
保证枚举是合法的 输出即可

CODE：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long a[1000010],f[1000010];
long long n,r,c;
bool check(int qwq)
{
	for(int i=0; i<=c-1; i++)
	   f[i]=0;
	for(int i=c; i<=n; i++)
	 {
	   f[i]=f[i-1]; 
	   if(a[i]-a[i-c+1]<=qwq)    //当前差值<最大差值
	     f[i]=f[i-c]+1;
	 }
	if(f[n]>=r)  //满足行数
	  return 1;
	else
	  return 0;
}
int main()
{
    cin>>n>>r>>c;
    for(int i=1; i<=n; i++)
     scanf("%lld",&a[i]);
    sort(a+1,a+1+n);  //排序
    int l=0,r=a[n]-a[1],mid;
    while(l<r)  //二分
     {
     	mid=(l+r)>>1;
     	if(check(mid))
     	  r=mid;
     	else
     	  l=mid+1;
     }
    cout<<l;
    return 0;
}