题解：P8088 『JROI-5』Autumn

_LogicFish_qwq · 2026-07-20 20:08:29 · 题解

Part 0: 准备工作

你需要知道什么是二分、二分怎么用。

Part 1: 思路

暴力的代码肯定能拿到部分分，但我要全部的。所以，我们需要优化。
题目问的是 \displaystyle\max_{i=1}^{n}\{d_{i}\}，翻译一下就是“每行第 k 大的里面，最大的那个”，同时还要取到最小的 \max 值。很明显是二分！

如果要求“最小的最大值”或者“最大的最小值”，那么大概率使用二分。

不过需要当心，只有答案满足单调性才可以二分。就是说，假设答案为 x 时成立，那么 x 往后（前）一定也成立；假设答案为 x 时不成立，那么 x 往前（后）一定也不成立。对于此题，很显然：得到了“最小的最大值”x，那么 x+1,x+2,\dots 也是满足条件的（它们一定比第 k 大更大）。反之，如果值 x 不满足，那么 x-1,x-2,\dots 也不满足（连前 k 个都没进，更不用说作为可选答案了）。
确定了用二分，接下来我们要问自己这些问题：

1. 二分分什么？
2. 二分边界（答案的最小最大值）在哪？
3. 判断条件是什么？
4. 条件成立后取更大的还是更小的？

我们一个个来看。

分的是什么数

显然，题目问什么我们答什么。既然是 \displaystyle\max_{i=1}^{n}\{d_{i}\}，那我们就对这个 \displaystyle\max_{i=1}^{n}\{d_{i}\} 进行二分。也就是，我们设当前答案为 x，那么满足的硬性条件是：交换之后，x 至少是第 k 大的，不然我们找到的这个 x 就是不合格的。

分的范围是什么

由于我们的操作不涉及到改数字，而题面给的数据范围是 1\le a_{i,j}\le 10^{18}，我们直接把下界 l 定成 1，把上界 r 定成 10^{18}，对吗？
有更好的实现。因为上述定范围的方法有个问题：有可能我们找到的数字不在题目给定的 a_{i,j} 中，所以不妨对出现的所有数字排个序，去重得到“出现过哪些数”，并以此作为二分的依据。

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        num[++tot]=a[i][j];//出现过的所有数
std::sort(num+1,num+tot+1);
tot=std::unique(num+1,num+tot+1)-num;//排序+去重，记录出现过的数字个数（不含相同数字，下标从 1 开始）
l=1,r=tot,mid;
//在后续的代码中，mid存储的是num中的下标，而非具体数字

判断条件是什么

接下来请“欣赏”我的雷霆抽象图例演示。
我们需要清楚的是，原数据中每一行（而非整个数组）的数字顺序不影响结果，那么我们干脆先排个序，还方便我们找大小。
为了方便演示，我们只考虑某两行的数。

上图虚线和 k 表示第 k 大的数，所在的位置。
接下来，假设我们当前二分到了数字 t：

我们能看出来，在第 k 位之后、在 t 之前的数字们，是 t 成功成为目标（第 k 大）的绊脚石阻碍。为了让 t 顺利登基来到第 k 的位置，我们得把这些数字换到别的地方去。

那么，和什么数换好呢？
当然是和比 \bm{t} 要小的数字。毕竟换来的数要是比 t 还大，那不就又拦着 t 上位了吗。此外还有什么条件呢？能换自己所在行的吗？不行，那样相当于没换（顺序不影响结果），所以要换就要换到其它行。
和其他行的什么换？和其它行的前 \bm{k} 个数换。为什么？因为只有这样才能保证其他行不会出现“顶替”现象。
就是说，没有和某行前 k 个数换，那么如果这一行前几个数特别大，导致换来的顺位往后挤，就会使“原来 \gt t 的值”被挤到第 k 位成为新的最大值，到别人地盘了你还拦着我是吧？

（大于 t 的值，使得最后的 \displaystyle\max_{i=1}^{n}\{d_{i}\} 不再是 t）
其他行的数字也是同理，只要在 a_{i,k} 之后、在 t 之前，都会拦着 t，毕竟我们要的是 t 成为这些数字里最大的。
因此，要换走的数，是“在 a_{i,k} 之后、在 t 之前，还比 t 大”的数字们，设个数是 gr；能拿来调换的数，是“在第 k 位之前、还比 t 小”的数字们，设个数是 ls。我们对其进行统计，然后看看是不是能在 x 次交换之内解决问题，就可以了。

（一种成功的换法，绿色框框里的数均比 t 小，因此会被挤到 t 的后面，不影响结果。同时红色框框里的“违规数字”比绿色的少，因此不会出现“顶替”现象。）
怎样才算“能在 x 次之内解决问题”呢？那必然是 gr\ge x 啊，只有这样才能确定每一个“违规数字”能被换开；此外，还必须要满足 ls\ge gr，只有这样才能保证“一个萝卜一个坑”，让每个“违规数字”能成功被换走。
以上就是判断函数里该实现什么，以及成立的条件是什么。

成功了要往哪里走

虽然求的值是“最大值”，但我们要最小化它，所以归根结底我们还是得往小了找——成功了，就找更小的；失败了，再退回来找大的。

Part 2: 代码

码风依然抽象，且其中涉及到 Lambda 表达式[^1]，我会在文章末尾简要说明。 :::success[AC Code]

//Someone tell Vedal there is a problem with my AI.
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
const int MAXN=2e3,INF=1e6+987;
int n,m,a[MAXN+5][MAXN+5],k,x;
int num[MAXN*MAXN+10],tot,ans;
void Init(),PreSolve(),Input(),Solve(),Answer(),AC();
signed main(){
    AC();
    return 0;
}
void Init(){
    std::ios::sync_with_stdio(false),
    std::cin.tie(0),std::cout.tie(0);
    #ifndef ONLINE_JUDGE
    std::freopen("FLIE.in" ,"r",stdin );
    std::freopen("FLIE.out","w",stdout);
    #endif
}
void AC(){
    Init();
    int T=1;
    //std::cin>>T;
    while(T--){
        PreSolve();
        Input();
        Solve();
        Answer();
    }
}
void PreSolve(){}
void Input(){
    std::cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) std::cin>>a[i][j],num[++tot]=a[i][j];
    std::cin>>k>>x;
}
void Solve(){
    std::sort(num+1,num+tot+1);
    tot=std::unique(num+1,num+tot+1)-num;
    for(int i=1;i<=n;i++)
        std::sort(a[i]+1,a[i]+m+1,[](int x,int y){return x>y;});//排序，使用 Lambda 函数简写
    int l=1,r=tot,mid;
    while(l<=r){//二分
        mid=l+r>>1;
        if([=]()->bool{//Lambda 函数，因为我懒得开新函数......
            int gr=0,ls=0;
            for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
                if(j>=k&&a[i][j]>num[mid]) gr++;
                else if(j<k&&a[i][j]<=num[mid]) ls++;//分别统计大数、小数(greater&less)
            }
            return gr<=x&&gr<=ls;//两条件
        }()) ans=mid,r=mid-1;//直接保存答案，再也不用记什么时候返回 l 啦！
        else l=mid+1;
    }
}
void Answer(){
    std::cout<<num[ans];//是下标！
}

:::

[^1]: 关于 Lambda 函数：简单来说，就是“原地开始写、不用命名”的函数，而且 Lambda 函数可以当做对象使用（差不多就是“函数类型的变量”）。基本语法如下：
[capture](parameters) -> return_type { body }
其中 capture 是“捕获列表”，用来决定怎么使用函数外的变量；parameters 是“参数列表”，和普通函数一样；return_type 是“返回类型”，当然你不写编译器会自己推断一个；body 是“函数体”，就是函数的实现。循环 while(l<=r) 里的代码中“捕获列表”里那个等号的意思是，“按值捕获”，就是只问数值，不会对其修改。
此外，在排序 sort(...,[](int x,int y){return x>y;}); 中，实现效果与 sort(..., cmp); 相同，其中函数 cmp 的定义是：bool cmp(int x,int y){return x>y;}。想了解更多关于 Lambda 函数的语法，可以去 OI wiki 等网站自行查阅。