$Description$

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

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

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

$Input$

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

接下来一行有 $N$ 个整数，代表 $N$ 个可以选择的数 $P_i$。

$Output$

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

$Sample$ $Input$

7 2 3
170 205 225 190 260 225 160

$Sample$ $Output$

30

$Hint$

对于 $50\%$ 的数据，$1\le N\le 1000$

对于所有数据，$1\le R,C\le 10^4,R\times C\le N\le 5*10^5,0 < P_i \le 10^9$。

$Train$ $of$ $Thought$

最大值最小
那就是二分了
我们先二分一个答案
然后贪心判断能否填R行

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;int A[500005], S[500005];
int n, r, c;int Check(int k)//判断最小值为k是否可行
{int  t = 0;for(int i = 1; i <= n - c + 1; ++i)if(S[i] <= k)t++, i += c - 1;return t >= r;
}
int main()
{scanf("%d%d%d", &n, &r, &c);for(int i = 1; i <= n; ++i)scanf("%d", &A[i]);sort(A + 1, A + n + 1);for(int i = 1; i <= n - c + 1; ++i)S[i] = A[i + c - 1] - A[i];//算i到i+c-1的最大差int left = 0, right = 1e9;while(left < right){int mid = (left + right) / 2;if(Check(mid))right = mid;else left = mid + 1;}printf("%d", right);return 0;
}