neuoj Blurred Pictures（小思维题

https://oj.neu.edu.cn/problem/1505

题意：一张由n*n的照片，每行从第ai个像素点到第bi个像素点是非模糊点，要求找出最大的正方形，该正方形中的像素都是非模糊点。

思路：这题有个很巧的地方"luckily, all the non-blurred pixels are connected in such a way that any horizontal or vertical line drawn between two non-blurred pixels goes only through non-blurred pixels. "

这就否定了以下这种情况，那就可以O(n)暴力移动边界了，枚举第1~n行为上边界，ans从1开始，然后对于第i行判定ans是否可行，若可行则ans++继续该行的判定，否则i++开始下一行的判定。每次判定只需判定上边界和下边界两行即可。

11111

11100

11111

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int l[maxn],r[maxn];
int n;

inline bool check(int up,int d){
    if(l[up]+d-1>r[up]) return false;
    if(up+d-1>n) return false;
    int down = up+d-1;
    int left = max(l[up],l[down]);
    if(left+d-1<=r[up]&&left+d-1<=r[down]) return true;
    return false;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n){
        for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
        int ans = 1;
        for(int i=1;i<=n;i++) {
            while(check(i,ans+1)) ++ans;
        }
        cout<<ans<<endl;
    }
    return 0;
}

neuoj Blurred Pictures（小思维题

相关推荐