个人赛3倒数第二题

CC 还非常喜欢探索世界，他给了你一张 n×nn \times nn×n 的地形图，希望从 (1,1)(1,1)(1,1) 点到达 (n,n)(n,n)(n,n) 点。 CC 可以从当前位置上下左右移动到达相邻格子，但 CC 不喜欢多余的运动，他希望行走路线尽可能平坦。（路线平坦度的定义为路线中海拔最高点与最低点之差） 请你帮 CC 计算出一条最平坦的路线的平坦度。 2 2 1 2 2 1 4 1 8 7 9 1 1 1 1 2 2 2 1 9 7 6 1 解题报告： 直接做不好统计，不妨反过来做。 O(2002)O(200^2)O(200​2​​) 枚举上下界限，然后在原图上跑 BFS 判断 更优秀的做法是枚举下界，二分上界，可以把复杂度降为 O(200log200K)O(200log200 K)O(200log200K) 比标程更优秀的方法是二分答案，然后枚举下界去跑 BFS

一定要用二分+ 枚举上下界写。。 自己想的最短路是错的。。

#include<bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define mem(a,b) memset(a,b,sizeof(a)); #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define MP make_pair #define ULL unsigned long long #define LL long long #define inf 0x3f3f3f3f #define md ((ll+rr)>>1) #define ls (i<<1) #define rs (ls|1) #define eps 1e-5 #define N 200 #define ree freopen("in.txt","r",stdin); #define bug pf("----------------"); typedef pair<int,int> pii; //2017年08月31日08:38:57 int n; int a[N][N]; bool vis[N][N]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; //inline int min(int a,int b){ //return a<b?a:b; //} bool dfs(int mi,int ma,int x,int y){ vis[x][y]=true; if(x==n&&y==n)return true; for(int i=0;i<4;++i){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]||a[nx][ny]<mi||a[nx][ny]>ma)continue; if(dfs(mi,ma,nx,ny))return true; } return false; } bool bfs(int mi,int ma,int aa,int bb){ queue<pii>q; q.push(MP(aa,bb)); //for(int k=1;k<=n;++k){ for(int g=1;g<=n;++g)vis[k][g]=false; } vis[aa][bb]=true; while(!q.empty()){ pii u=q.front();q.pop(); int x=u.first;int y=u.second; if(x==n&&y==n)return true; for(int i=0;i<4;++i){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]||a[nx][ny]<mi||a[nx][ny]>ma)continue; vis[nx][ny]=true;q.push(MP(nx,ny)); } } return false; } int ans; bool judge(int mid){ for(int i=0;i<=a[1][1];++i){ int down=i,up=i+mid; if(a[1][1]<down||a[1][1]>up)continue; mem(vis,0); if(dfs(i,i+mid,1,1))return true; } return false; } void Find(int l,int r){ while(l<=r){ int mid=(l+r)>>1; if(judge(mid))ans=mid,r=mid-1; else l=mid+1; //pf("%d\n",mid); } } int main(){ int T;sf("%d",&T); while(T--){ sf("%d",&n); int mi=inf,ma=0; rep(i,1,n){ rep(j,1,n){sf("%d",&a[i][j]);mi=min(mi,a[i][j]),ma=max(ma,a[i][j]);} } ans=inf; Find(abs(a[1][1]-a[n][n]),ma-mi); //for(int i=0;i<=a[1][1];++i){ //int l=i,r=ma; //int cnt=-1; //while(l<=r){ //int mid=(l+r)>>1; //for(int k=1;k<=n;++k){ for(int g=1;g<=n;++g)vis[k][g]=false; } //if(bfs(i,mid,1,1)){cnt=mid;r=mid-1;} //else l=mid+1; //} //if(cnt!=-1) ans=min(ans,cnt-i); //} //for(int i=mi;i<=ma;++i){ //for(int j=i;j<=i+ans;++j){ //for(int k=1;k<=n;++k){ for(int g=1;g<=n;++g)vis[k][g]=false; } //if(bfs(i,j,1,1))ans=min(ans,j-i); //} //} pf("%d\n",ans); } }