自动搬运

查看原文

来自洛谷，原作者为

	FallingFYC_ 但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。

搬运于2025-08-24 22:50:55，当前版本为作者最后更新于2023-11-21 20:22:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

原题

分析&思路

可以用二分答案解决。关键在于 check 函数，它可以这么写：题目中说每次只能向右或向下走，所以每一步的横坐标肯定都大于等于上一步，可以使用一个变量 lstx 记录，因此当某个点小于 check 函数传入的答案并且当前点的横坐标要比前一个小时，就说明这个答案不对，否则当前点的横坐标大于等于前一个时，更新 lstx。

注意：由于 $n$ 和 $m$ 的范围，不能用二维数组存，需要压维。

代码：

#include <bits/stdc++.h>
using namespace std;
int t , n , m , a[(int)1e6 + 5] , ans;

bool check(int mina)
{
    int lstx = 1;
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= m ; j++)
            if (a[(i - 1) * m + j] < mina)
            {
                if (lstx <= j) lstx = j;
                else return false;
            }
    return true;
}

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1 ; i <= n * m ; i++) cin >> a[i];
        ans = 0;
        int l = 0 , r = n * m , mid;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (check(mid)) {ans = mid; l = mid + 1;}
            else r = mid - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}