[[GDCPC2023] Path Planning]

FallingFYC_ · 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;
}