题解：P15197 [SWERC 2018] Blurred Pictures

· · 题解

前言

本篇题解的解题方法为：单调队列，二分答案。

题目大意

觉得题目难理解的，可以试试结合样例理解。

:::info[题目] Damon 喜欢为他旅行中所到之处拍摄照片，并将它们装入相框。他所有的照片都是 N \times N 像素的正方形格式。他从巴黎带回了许多纪念碑（如埃菲尔铁塔或卢浮宫）的美丽照片，但不幸的是，当他回到家时，他发现所有照片在“好”（即非模糊）的部分都模糊了，而且幸运的是，所有非模糊像素的连接方式使得任意两个非模糊像素之间绘制的水平线或垂直线只经过非模糊像素。为了从他失败的照片中获取最佳效果，他决定从每张照片中切割出可能最大的、不含任何模糊像素的图片。由于他的相框都是正方形的，出于美观原因，切割出的图片也必须是正方形。Damon 不希望他的图片倾斜，因此要求切割出的正方形的边与原始图片的边平行。

重要提示

题目其实就是：

给 N 行，每行给出清晰区间的端点 [a_i,b_i]。

找出在这个图像中最大的清晰正方形边长。

注意，正方形的边必须与图片的边平行！

解题思路

因为这道题具有单调性，所以我们可以用二分答案。

如果边长 k 可行，

那么边长 k-1 一定也可行。

如果边长 k 不可行，

那么边长 k+1 一定也不可行。

写一个 bool check(int k) 函数，检查边长为 k 的正方形是否存在于图像中。

在 check(k) 中，我们需要对每个长度为 k 的连续行窗口，快速求出：

如果每次重新遍历窗口内所有元素，复杂度是 O(k)，整体 check(k) 就会变成 O(N \times k)，最坏情况 O(N^2)，会超时。

单调队列可以在 O(1) 时间内获取窗口的最值，每个元素入队出队一次，总复杂度 O(N)。

不会的可以去看看 P1886 【模板】单调队列 / 滑动窗口，这道题是单调队列的模板题。

时间复杂度：

对于数据范围 N \le 10^5 不会超时。

代码实现

我们可以使用 STL 中的 deque 来写单调队列，节省空间。

在主函数进行二分。

AC 代码

#include <bits/stdc++.h>
using namespace std;

int n,a[100005],b[100005];

bool check(int k){
    deque <int> q1,q2;
    for(int i=1;i<=n;i++){
        while(!q1.empty() && a[q1.back()]<=a[i]) q1.pop_back();
        q1.push_back(i); 
        while (!q2.empty() && b[q2.back()]>=b[i]) q2.pop_back();
        q2.push_back(i);
        if(i>=k){
            if(q1.front()==i-k) q1.pop_front();
            if(q2.front()==i-k) q2.pop_front();
            if(a[q1.front()]<=b[q2.front()]-k+1) return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    int l=1,r=n,ans=1;
    while(l<=r){
        int mid=(r+l)/2;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}

record

后记

这是本蒟蒻的第 4 篇题解，求过。

给个赞再走呗！