大体方向上是正确的。但是,代码处理时我做的不好。
我也意识到了,老老实实地枚举的话,时间复杂度一定是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()); }