自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:35:51，当前版本为作者最后更新于2022-02-01 22:28:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

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

由于我们需要计算矩阵的每一行的第 $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;
}