大体方向上是正确的。但是,代码处理时我做的不好。
我也意识到了,老老实实地枚举的话,时间复杂度一定是10^9级别的。
如何优化呢?我也注意到了,在枚举向右地次数的时候是有一个单调性的。
对于每一个robot,能够检测到他的点一定是越来越少。
我们只用先对监视器和robot排序,就可以利用这个单调性了。
但是,即使如此,我仍然tle了。
我的做法其实已经和正确答案差不多了,思想史类似的。
但是我的常数太大了,所以被卡。
然后,我看了正确答案。
正确做法是,先筛选出所有的监控监视robot的情况。
然后再进行排序,执行上面的类似的操作。
常数很小。跑得很快。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> pii;
const int max_n = 2200;
pii a[max_n],b[max_n],c[max_n*max_n];
int d[max_n*max_n];
int n,m;
int cnt = 0;
int Solve(){
    for (int i=1;i <= n;++i)
    for (int j=1;j<=m;++j)
    if (a[i].first<=b[j].first&&a[i].second<=b[j].second)
    c[++cnt] = {b[j].first-a[i].first+1,b[j].second-a[i].second+1};
    sort(c+1,c+1+cnt);

    d[cnt+1]=0;
    for (int i=cnt;i>=1;--i)d[i]=max(d[i+1],c[i].second);
    int pos = 1;int ans = 2e6;
    for (int i=0;i<=1e6;++i){
        while (pos<=cnt&&c[pos].first<=i)++pos;
        ans = min(ans,d[pos]+i);
    }
    return ans;
}

int main(){
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;++i)scanf("%d %d",&a[i].first,&a[i].second);
    for (int i=1;i<=m;++i)scanf("%d %d",&b[i].first,&b[i].second);
    printf("%d\n",Solve());
}