題目鏈接：點擊查看

題目大意：在二維平面坐標系上有 n 個海盜和 m 個探照燈，假設海盜 i 的位置為 ( a[ i ] , b[ i ] )，探照燈 j 的位置為 ( c[ j ] , d[ j ] )，如果滿足 a[ i ] <= c[ j ] && b[ i ] <= d[ j ] ，則海盜 i 會被探照燈 j 發現，現在每次操作可以將所有 n 個海盜同時向上、下、左、右選擇一個方向移動一個單位，問最小需要多少次操作，才能使得 n 個海盜都不被發現

題目分析：比較顯然的一點是，在 x 方向只需要向上走，在 y 方向只需要向右走，又因為 x 和 y 的取值范圍是小于等于 1e6 的，所以可以枚舉在 x 方向上走多少步，然后去計算答案

貪心去想，假如現在枚舉在 x 方向上走了 xx 步，如果向上走 xx 步可以脫離探照燈范圍的海盜肯定是直接逃離了，剩下的不能逃離的海盜，則需要通過向右走 yy 步才能逃離，我們只需要想辦法快速計算一下這個 yy 即可

不難發現只需要儲存一下每個 xx 臨界時 yy 的最大值即可，這樣維護一個后綴最大值就是相應的 yy 了

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e3+100;int a[N],b[N],c[N],d[N];int cnt[N*N];int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",a+i,b+i);for(int i=1;i<=m;i++)scanf("%d%d",c+i,d+i);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i]<=c[j])cnt[c[j]-a[i]]=max(cnt[c[j]-a[i]],d[j]-b[i]+1);int mmax=0,ans=1000001;for(int i=1000001;i>=0;i--)//i是xx,mmax是yy{mmax=max(mmax,cnt[i]);ans=min(ans,i+mmax);}printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1408D Searchlights(思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。