原题：https://codeforces.ml/contest/1408/problem/D
题意：
有n个人 m个手电筒。给出所有人和手电筒的坐标。 当x人>x手电筒或者y人>y手电筒时人安全。
有两种操作，①给所有人的x加1②给所有人的y加1
问至少操作多少次让所有人都安全
参考博客：https://www.baidu.com/link?url=5s7Wu90rVh3CDRssKWUsMBw4hXVjqg_cYNGHjxUEncZq9fOhsng4eZJI0O3kRETNca_NjOtUP6pywK4CXFK31PPciLVRNSiOeOqziKE_1L7&wd=&eqid=c56cfa8d000cdba2000000035f756bbe
思路：
先求出所有Δx对应的Δy
然后遍历所有的Δx取值，找max（Δx+Δy）
具体实现：
①怎么求出所有所有Δx对应的Δy？
两重循环 对每一个人遍历所有的手电筒，Δx=c[j]-a[i]
当a[i]<=c[j]时 在横坐标上无法使人安全，所以需要Δy=d[j]-b[i] 在遍历中找到最大的Δy
1 for(ll i=1;i<=n;i++){ 2 for(ll j=1;j<=m;j++){ 3 if(a[i]<=c[j]&&d[j]>=b[i]){ 4 needy[c[j]-a[i]]=max(needy[c[j]-a[i]], d[j]-b[i]+1); 5 //如果在x方向补上c[j]-a[i] Δx=c[j]-a[i]; 6 //对于a[i]<=c[j]的来说 补上后还是不能满足不被看到的条件 所以需要在y上超于d[j] 7 //所以它至少需要在y上增加d[j]-b[i]+1（取所有情况中的最大值） 8 } 9 } 10 }
②怎么实现遍历所有的Δx取值，找max（Δx+Δy）？
需要注意上一步中存储的是“恰好Δx” 在一些情况中增加的x不一定为在上面的循环中出现过的c[j]-a[i]
所以需要变量realneed来存储当前的Δy
1 ll res=2*inf; 2 ll realneed=0; 3 for(ll i=1e6;i>=0;i--){ 4 /* 5 * 设x有效 x-1无效 6 * 说明 有点与手电筒距离之差为x 但没有x-1 7 * 那么横坐标加上x和x-1没有区别 因为都不能走到安全区域（要加上x+1 8 * 所以他们的needy是相同的 9 * 而在needy数组中 x-1没有出现 needy为0 不对 10 * 所以要用realneed来记录真正需要增加的y，对x-1来说就是之前的（i从大到小遍历）最近的一个有效needy 11 */ 12 if(needy[i]>realneed) realneed=needy[i]; 13 res=min(res, i+realneed); 14 }
完整代码：
1 #include "iostream" 2 #include "stdio.h" 3 #include "stdlib.h" 4 #include "iomanip" 5 using namespace std; 6 typedef long long ll; 7 const ll mx=2e3+10; 8 const ll inf=1e6+10; 9 ll n, m; 10 ll a[mx], b[mx]; 11 ll c[mx], d[mx]; 12 ll needy[inf]; 13 ll read(){ 14 ll sum=0; 15 char c=getchar(); 16 while(c!=‘ ‘&&c!=‘\n‘){ 17 sum=sum*10+(ll)(c-‘0‘); 18 c=getchar(); 19 } 20 return sum; 21 } 22 23 int main() { 24 n=read(), m=read(); 25 for(ll i=1;i<=n;i++) a[i]=read(), b[i]=read(); 26 for(ll i=1;i<=m;i++) c[i]=read(), d[i]=read(); 27 28 for(ll i=1;i<=n;i++){ 29 for(ll j=1;j<=m;j++){ 30 if(a[i]<=c[j]&&d[j]>=b[i]){ 31 needy[c[j]-a[i]]=max(needy[c[j]-a[i]], d[j]-b[i]+1); 32 //如果在x方向补上c[j]-a[i] Δx=c[j]-a[i]; 33 //对于a[i]<=c[j]的来说 补上后还是不能满足不被看到的条件 所以需要在y上超于d[j] 34 //所以它至少需要在y上增加d[j]-b[i]+1（取所有情况中的最大值） 35 } 36 } 37 } 38 ll res=2*inf; 39 ll realneed=0; 40 for(ll i=1e6;i>=0;i--){ 41 /* 42 * 设x有效 x-1无效 43 * 说明 有点与手电筒距离之差为x 但没有x-1 44 * 那么横坐标加上x和x-1没有区别 因为都不能走到安全区域（要加上x+1 45 * 所以他们的needy是相同的 46 * 而在needy数组中 x-1没有出现 needy为0 不对 47 * 所以要用realneed来记录真正需要增加的y，对x-1来说就是之前的（i从大到小遍历）最近的一个有效needy 48 */ 49 if(needy[i]>realneed) realneed=needy[i]; 50 res=min(res, i+realneed); 51 } 52 printf("%lld\n", res); 53 }
CFGrakn Forces 2020 D. Searchlights
原文：https://www.cnblogs.com/sloth612/p/13759325.html