Description:

在麦克雷的面前有N个数，以及一个RC的矩阵。现在他的任务是从N个数中取出 RC 个，并填入这个矩阵中。矩阵每一行的法值为本行最大值与最小值的差，而整个矩阵的法值为每一行的法值的最大值。现在，麦克雷想知道矩阵的最小法值是多少。

Input:

输入共两行。

第一行是三个整数：n，r，c。（ r , c &lt; = 1 0 4 r, c &lt;= 10^{4} r,c<=104 , r ∗ c &lt; = n &lt; = 1 0 6 r * c &lt;= n &lt;= 10_{6} r∗c<=n<=106​）

第二行是 n 个整数 Pi。( 0 &lt; p i &lt; = 1 0 9 0 &lt; pi &lt;= 10^{9} 0<pi<=109 )

Output:

输出一个整数，即满足条件的最小的法值。

Sample Input:

7 2 3
170 205 225 190 260 225 160

Sample Output:

30

题目连接

题目最优情况肯定是按照顺序放入的，所以将输入的n个数排序后用一个数组存储c个数之间最大值和最小值的差值，二分找结果n，如果n可以有r行数据则继续缩小右边界以找到最小n，否则增大左边界，直至找到唯一最小n输出结果。

AC代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

int n;
int r, c;
int p[maxn];
int magic[maxn];

bool judge(int x) {
    int i = c - 1;
    int cnt = 0;
    while (i < n) {
        if (magic[i] <= x) {
            cnt++;
            i += c;
            if (cnt >= r) [
                return 1;
            ]
        }
        else {
            i++;
        }
    }
    return 0;
}

int main() {
    //fropen("in.txt", "r", stdin);
    cin >> n >> r >> c;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    sort(p, p + n);
    for (int i = c - 1; i < n; ++i) {
        magic[i] = p[i] - p[i - c  + 1];
    }
    int _left = 0, _right = 1e10+5;
    while (_left < _right) {
        int mid = (_left + _right) >> 1;
        if (judge(mid)) {
            _right = mid;
        }
        else {
            _left = mid + 1;
        }
    }
    cout << _left;
    return 0;
}