CF1408D | 总结模型

分析：首先小偷要躲过每一个灯塔 小偷躲过一个灯塔只需要横坐标或纵坐标大于即可

想到可以处理处每个小偷相对每个灯塔最少移动步数<ax,ay>分别表示纵坐标或者横坐标移动数

一组<ax,ay>只需要我们满足其中一个即可 这就回到一个模型上面

转化到这个模型上面还是有一定的难度的

https://zhuanlan.zhihu.com/p/268630329

#include<bits/stdc++.h>using namespace std;#define lowbit(x) x&(-x)#define ll long longconst int maxn=2005;const int maxx=4e6+5;int n,m,cnt,tot;struct node{int x,y;}a[maxn],b[maxn],res[maxx],ans[maxn];bool cmp(node aa,node bb){if(aa.x!=bb.x)return aa.x<bb.x;return aa.y<bb.y;}int main(){cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);for(int i=1;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);    for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)    {int len1=b[j].x-a[i].x+1;int len2=b[j].y-a[i].y+1;if(len1<=0||len2<=0)continue;res[++tot].x=len1;res[tot].y=len2; }}sort(res+1,res+1+tot,cmp);int pre=-1;for(int i=tot;i>=1;i--)if(res[i].y>pre){ans[++cnt].x=res[i].x;ans[cnt].y=res[i].y;pre=res[i].y;}int sum=1e9;for(int i=1;i<=cnt+1;i++)sum=min(sum,ans[i].x+ans[i-1].y);cout<<sum<<endl;return 0;}