[CF1408D] Searchlights

Description

有 (n) 个坐标为 ((a_i,b_i)) 的人，有 (m) 个坐标为 ((c_i,d_i)) 的灯。

每次操作，要么让所有 (a_i+1)，要么让所有 (b_i+1)。

如果一个人的横纵坐标都不大于灯的横纵坐标，那么这个人是安全的。

求最小移动多少次使得所有人都是安全的。

Solution

设人的编号为 (i)，灯的编号为 (j)，则对于任意 (i,j)，以下两式必须要有至少一个成立：(x+a[i] > c[i],y+b[i] > d[i])

假设将一个人移动到 ((x,y))，设 (x le c[j]-a[i])，那么 (y ge d[j]-b[i]+1)。

于是我们在 (x=c[j]-a[i]) 的位置上打一个 (d[j]-b[i]+1) 的 (max) 标记，最后对所有标记做一次后缀 (max) 即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 5005;
const int M = 1000005;

int n,m,a[N],b[N],c[N],d[N],f[M];

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=m;i++) cin>>c[i]>>d[i];

    for(int i=1;i<=n;i++) 
    {
        for(int j=1;j<=m;j++)
        {
            if(c[j]-a[i]>=0)
            {
                f[c[j]-a[i]]=max(f[c[j]-a[i]],d[j]-b[i]+1);
            }
        }
    }

    for(int i=M-1;i>=0;i--) f[i]=max(f[i],f[i+1]);

    int ans=1e18;

    for(int i=0;i<M;i++) ans=min(ans,i+f[i]);

    cout<<ans<<endl;
}