题解 P8088 【『JROI-5』Autumn】

· · 题解

题解

一种容易想到的思路是，二分答案，然后判断是否存在一种合法方案。

由于我们需要计算矩阵的每一行的第 k 大，因此考虑先将每一行进行排序。对于样例，排序后是这个模样：

\newcommand{\line}[5]{ \mathclap{#1} & \mathclap{#2} & \mathclap{#3} & \mathclap{#4} & \mathclap{#5} } \def\b{\rule{1.8em}{1.8em}} \def\r#1{\raisebox{.5em}{#1}} \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}}\cr[-18pt] \line{1}{2}{3}{4}{5} \cr\hline \line{1}{2}{3}{4}{5} \cr\hline \line{6}{7}{8}{9}{10} \cr\hline \line{1}{2}{3}{4}{5} \cr\hline \line{1}{2}{3}{4}{5} \cr\hline \end{array}

那么每一行的第 n-k+1 列，就是该行的第 k 大。

假定现在二分的答案为 d。那么存在一种方案使得「每一行的第 k 大」的最大值不超过 d，等价于我们要在每一行都有至少 n-k+1 个不大于 d 的数字。那么可以把数字分为两类：不大于 d 的数字，和大于 d 的数字。将其黑白染色，前者染成白色，后者染为黑色。以样例举例，假设现在 d=7。

\newcommand{\line}[5]{ \mathclap{#1} & \mathclap{#2} & \mathclap{#3} & \mathclap{#4} & \mathclap{#5} } \def\bb{\color{black}\rule{1.8em}{1.8em}} \def\wb{\color{white}\rule{1.7em}{1.8em}} \def\r#1{\raisebox{.5em}{#1}} \phantom{\kern{-19.5pt}\left|\phantom{\rule{1em}{5.5em}}\right.} \phantom{\kern{-20.5pt}\left|\phantom{\rule{1em}{5.5em}}\right.} \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}} & \phantom{\rule{.75em}{1em}}\cr[-18pt] \line{\wb}{\wb}{\wb}{\wb}{\wb} \cr[-5pt]\hline \line{\wb}{\wb}{\wb}{\wb}{\wb} \cr[-5pt]\hline \line{\wb}{\wb}{\bb}{\bb}{\bb} \cr[-5pt]\hline \line{\wb}{\wb}{\wb}{\wb}{\wb} \cr[-5pt]\hline \line{\wb}{\wb}{\wb}{\wb}{\wb} \cr[-5pt]\hline \end{array} \kern{-19.5pt}\left|\phantom{\rule{1em}{5.5em}}\right. \kern{-20.5pt}\left|\phantom{\rule{1em}{5.5em}}\right.

那么我们需要把 n-k+1 这条线（图中的双线）右侧的两个白色方块与 n-k+1 左侧的两个黑块互换位置。

假设 n-k+1 左侧黑块的个数为 p，右侧白块的个数为 q。那么当且仅当 p\le q 且 p\le x 时可以使得「每一行的第 k 大」的最大值不超过 d。

直接这么做，复杂度是 \mathcal O(\log v\cdot nm) 的，卡卡常勉强能过。不过可以发现，如果我们让枚举的 d 从大到小变化，那么 p 应该是单调不减，q 应该是单调不增的。那么只需要对于 a_{i,j} 从大到小作为可能的 d，就可以单调地维护 p 和 q 的值。均摊一下这部分的时间复杂度就降为了 \mathcal O(nm)。不过由于需要对于所有数字排序，所以复杂度是 \mathcal O(\log (nm)\cdot nm)，但是常数可能小一点（因为 \text{STL} 当中的 sort 速度比较快）。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN=2e3+3,MAXM=4e6+3;
i64 n,m,k,u,A[MAXN],t;
i64 qread(){
    i64 w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
i64 W[MAXM][2],I[MAXM],ans=1e18,p,q,x,y;
bool cmp(int a,int b){return W[a][0]<W[b][0];}
int main(){
    n=qread(),m=qread();
    up(1,n,i){
        up(1,m,j) A[j]=qread(); sort(A+1,A+1+m);
        up(1,m,j){
            W[++t][0]=A[j],W[t][1]=j,I[t]=t;
        }
    }
    k=m-qread()+1,u=qread(),sort(I+1,I+1+t,cmp);
    x=t,p=n*(m-k),y=t,q=0;
    dn(t,1,i){
        i64 d=W[I[i]][0];
        while(x>0&&W[I[x]][0]>d) p-=(W[I[x]][1]> k),--x;
        while(y>0&&W[I[y]][0]>d) q+=(W[I[y]][1]<=k),--y;
        if(q>u||q>p) break; ans=d;
    }
    printf("%lld\n",ans);
    return 0;
}