【zzuli-2259】matrix

题目描述

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

输入

输入共两行。

第一行是三个整数：n，r，c。（r, c <= 104, r * c <= n <= 106）

第二行是 n 个整数 Pi。(0 < pi <= 109)

输出

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

样例输入

7 2 3

170 205 225 190 260 225 160

样例输出

30

引用殷大佬一句话，「最大最小值我一看就是二分」....orz

首先每一行的元素一定是连续的，但是不同行的元素可以不连续，这点很容易想明白。求min，等号应该加在r = mid - 1，答案是l。然后题目就变成了判断一个数是否是一个矩阵的法值，方法是枚举每个长度为c的行看看max-min是否<=法值，满足r个则成立，否则不成立。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+;

int mp[N], a[N], R, c, n;

bool ok(int x)

{

    int num = ;

    for(int i = c; i <= n; i++)

    {

        if(a[i] <= x) //等号体现在这里

        {

            i = i+c-;

            num++;

        }

        if(num == R) return ;

    }

    return ;

}

int main()

{

    cin>>n>>R>>c;

    for(int i = ; i <= n; i++) scanf("%d", &mp[i]);

    sort(mp+, mp++n);

    for(int i = c; i <= n; i++) a[i] = mp[i] - mp[i-c+];

    int l = , r = 1e9;

    while(l <= r)

    {

        int mid = (l+r)>>;

        if(ok(mid))

            r = mid - ;

        else

            l = mid + ;

    }

    printf("%d\n", l);

    return ;

}