CodeForces - 1408D - Searchlights 思维贪心

    科技2022-07-17  102

    CodeForces - 1408D - Searchlights 思维

    题意:给出n个强盗坐标 ( a i , b i ) (a_i,b_i) (ai,bi),m个探照灯坐标 ( c j , d j ) (c_j,d_j) (cj,dj),每一次可以将所有 a i + 1 a_i+1 ai+1或者 b i + 1 b_i+1 bi+1,对于 1 ≤ i ≤ n , 1 ≤ j ≤ m 1\leq i\leq n,1\leq j\leq m 1in,1jm,均满足 a i ≤ c j & & b i ≤ d j a_i\leq c_j\&\&b_i\leq d_j aicj&&bidj,问最少需要操作几次

    想不出来 抄的题解

    做法一:假设现在全体向右移动 i i i个距离

    对于那些水平距离 ( c j − a i ) (c_j-a_i) (cjai)小于 i i i的,就可以直接出去了对于那些水平距离大于等于 i i i的,就只能通过向上移动才能出去了,答案就是 i + i+ i+{加上他们当中向上移动所需最大步数}

    如果我们正向遍历 i i i,就会遇到一个问题,当向右的移动距离为 i i i时,水平距离 > = i >=i >=i的那些对,最大的向上移动步数该怎么求?

    于是想到逆向遍历,通过后缀最大值记录下当前 > = i >=i >=i的最大所需向上步数,在 ( = i ) (=i) (=i)的时候更新这个后缀最大值

    复杂度是 O ( N ) O(N) ON

    代码:

    const int maxn=2e6+7; const int INF=0x3f3f3f3f; const ll INFF=1e18; int n,m,maxx=0,ans=INF,up[maxn]; struct node { int x,y; }p[maxn],pp[maxn]; int main() { scanf("%d%d",&n,&m); mem(up,0); rep(i,1,n)scanf("%d%d",&p[i].x,&p[i].y); rep(i,1,m) { scanf("%d%d",&pp[i].x,&pp[i].y); rep(j,1,n) if (p[j].x<=pp[i].x&&p[j].y<=pp[i].y) up[pp[i].x-p[j].x]=max(up[pp[i].x-p[j].x],pp[i].y-p[j].y+1); } for (int i=1000000;i>=0;i--) { maxx=max(maxx,up[i]); ans=min(ans,i+maxx); } W(ans); return 0; } }


    做法二:将所有的点对 ( i , j ) (i,j) (i,j)拆成一个独立的项,那么它拥有两个值,一个是向上多少步可以出去(如果已经出去就是0),另一个是向右多少步可以出去 将这些点对按向右多少步排序,假设向右 a [ i ] a[i] a[i]步可以出去,那么向右 a [ 1 ] 、 a [ 2 ] . . . a [ i − 1 ] a[1]、a[2]...a[i-1] a[1]a[2]...a[i1]步的都可以成功出去,剩下的 i , i + 1... n i,i+1...n i,i+1...n就得在向上的步数里面取最大值,显然这是一个后缀最大值就可以O(1)读取了 由于加了个排序,所以复杂度是 O ( N l o g N ) O(NlogN) ONlogN

    代码:

    const int maxn=4e6+7; const int INF=0x3f3f3f3f; const ll INFF=1e18; int n,m,maxx[maxn],tot=0,ans=INF; struct node { int x,y; }p[maxn],a[maxn],b[maxn]; bool cmp(node a,node b){return a.x<b.x;} int main() { scanf("%d%d",&n,&m); mem(maxx,0); rep(i,1,n)scanf("%d%d",&a[i].x,&a[i].y); rep(i,1,m)scanf("%d%d",&b[i].x,&b[i].y); rep(i,1,n) { rep(j,1,m) { if (a[i].x<=b[j].x&&a[i].y<=b[j].y) { p[++tot].x=b[j].x-a[i].x+1; p[tot].y=b[j].y-a[i].y+1; } else { p[++tot].x=0; p[tot].y=0; } } } sort(p+1,p+1+tot,cmp); p[0].x=0;p[0].y=0;maxx[tot+1]=0; for (int i=tot;i>=0;i--) { if (i==tot)maxx[i]=p[i].y; else maxx[i]=max(maxx[i+1],p[i].y); } rep(i,0,tot)ans=min(ans,p[i].x+maxx[i+1]); W(ans); return 0; }
    Processed: 0.012, SQL: 8