CF1825B LuoTianyi and the Table 题解

考虑下面的一种情况：

\[1,\ 2,\ 3,\ 4,\ 5,\ 6\]

\[ \def\arraystretch{1.5} \begin{array}{c:c:c} \ &\ &\ \\\hline \ &\ &\ \end{array} \]

选择子矩阵从左上角开始，所以要使答案最大，左上角的值无非只有两种情况：最大**和**最小。

sort(a+1,a+1+n*m);

先来看看填最大值：

\[1,\ 2,\ 3,\ 4,\ 5,\ {\color{red}6}\]

\[ \def\arraystretch{1.5} \begin{array}{c:c:c} \color{green}6&\color{orange}\_&\ \\\hline \color{pink}\_&\ &\ \end{array} \]

此时，这个 \(6\) 旁边有两个空位，那么任意一个子矩阵（除了 \(6\) 本身构成的）都会包含这两个空位当中的一个（或全部）。

那么，我们就要让其中一个填上最小值，另一个填上次小值。

很显然，我们要让较短的那一边的那个空位填上次小值，另一个填最大值，这样能够保证答案最大（这样的话，只有 \(\mathrm{len_{\text{较短的边}}}-1\) 个子矩阵的答案是最大值减次小值，而其他的都是最大值减最小值）。

\[{\color{red}1},\ {\color{red}2},\ 3,\ 4,\ 5,\ {\color{red}6}\]

\[ \def\arraystretch{1.5} \begin{array}{c:c:c} \color{green}6&\color{orange}1&\ \\\hline \color{pink}2&\ &\ \end{array} \]

剩下的就随便填了，因为每个子矩阵的答案已经是最大值减去最小值（或次小值）了。

\[\color{green}1,\ 2,\ 3,\ 4,\ 5,\ 6\]

\[ \def\arraystretch{1.5} \begin{array}{c:c:c} \color{green}6&\color{orange}1&3\\\hline \color{pink}2&5&4 \end{array} \]

值为：\(0+5+5+4+5+5=24\)。

tmp = min(n,m)-1;
ans1 = (n*m-tmp-1) * (a[n*m]-a[1]) + tmp * (a[n*m]-a[2]);
// 最大值与最小值同时包含的子矩阵共有 (n*m-min(n,m)-1) 个。
// 最大值与次小值同时包含的子矩阵共有 (min(n,m)-1) 个。
// 减掉的那个 1 是因为左上角这个自己减自己等于零。

再来看看填最小值：

最小值其实与最大值同理，不过填的那两个最小值、次小值变成了最大值、次大值。

\[\color{green}1,\ 2,\ 3,\ 4,\ 5,\ 6\]

\[ \def\arraystretch{1.5} \begin{array}{c:c:c} \color{green}1&\color{orange}6&4\\\hline \color{pink}5&3&2 \end{array} \]

值为：\(0+5+5+4+5+5=24\)。

ans2 = (n*m-tmp-1) * (a[n*m]-a[1]) + tmp * (a[n*m-1]-a[1]);

综上，答案为 \(\max(24, 24)=24\)。

cout<<max(ans1,ans2)<<endl;

有人可能觉得两种只需要算一种就行了，其实样例一就很好地否认了这个观点。

\[1,\ 3,\ 1,\ 4\]

\[ \def\arraystretch{1.5} \begin{array}{c:c} \color{green}4&\color{orange}1\\\hline \color{pink}1&3 \end{array} \]

\[ \def\arraystretch{1.5} \begin{array}{c:c} \color{green}1&\color{orange}4\\\hline \color{pink}3&1 \end{array} \]

答案为 \(\max(9, 8)=9\)。

讲完了，撒花！完整代码如下：

// 珍爱账号，请勿贺题
#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr static int NxM = 1e4+1;
int n,m,a[NxM],tmp,ans1,ans2;

void solve() {
    cin>>n>>m;
    for (int i=1; i<=n*m; i++) cin>>a[i];
    sort(a+1,a+n*m+1);

    tmp = min(n,m)-1;
    ans1 = (n*m-tmp-1) * (a[n*m]-a[1]) + tmp * (a[n*m]-a[2]);
    ans2 = (n*m-tmp-1) * (a[n*m]-a[1]) + tmp * (a[n*m-1]-a[1]);

    cout<<max(ans1,ans2)<<endl;
}

int T;
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while (T--) solve();

    return 0;
}

CF1825B LuoTianyi and the Table 题解

评论