最小差异矩阵

Posted on Edited on In

题目大意：有一个\(n \times m\)的矩阵，矩阵的每个位置上可以放置一个数。对于第 i 行，第 i 行的差异定义为该行的最大数和最小数的差。一个矩阵的差异，定义为矩阵中每一行差异的最大值。现在给定 k 个数 v[1..k]，问：从这 k 个数中选 \(n\times m\)个数放入矩阵，能够得到的矩阵的差异最小值是多少。

看到最小值最大，最大值最小，就考虑二分答案

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define int long long
using namespace std;

const int N = 1e6 + 66;

int k, n, m, a[N];

inline int judge(int x)
{
    int i, pd = 0;
    for (i = 1; i + m - 1 <= k; ++ i)
    {
        if (a[i + m - 1] - a[i] <= x)
        {
            ++ pd, i = i + m - 1;
        }
    }
    return pd >= n;
}

signed main()
{
    int i;
    k = read(), n = read(), m = read();
    for (i = 1; i <= k; ++ i) a[i] = read();
    sort(a + 1, a + k + 1);
    int l = 0, r = 1e9 + 66, mid;

    while (l < r)
    {
        mid = (l + r) >> 1;
        if (judge(mid)) r = mid;
        else l = mid + 1;
    }

    put(l);
    return 0;
}

总结：这次考试期望得分30+30pts，第一题挂了10分

如果说按照期望得分的话，我貌似还可以，但是这个期望得分太低

别人都可以切掉第一题，但是我考试时候脑子不知道怎么想的，就是没想到二分答案，我真是个**

这次考试的收获：

  • 1.最大值最小，最小之最大，一定一定与二分答案有关
  • 2.会写对拍了，再也不用复制原来的了