╰(￣▽￣)╭

有一个居住在多山岛屿的登山家，已经攀上了一座山峰，并且要攀爬另外一座更高的山峰。

更精确地说，岛上的每一点都有一个大于零的海拔（海面的海拔为零），并且如果登山家位于海拔Ei的山峰上，那么他的目标是到达其他海拔为Ej（Ej>Ei）的山峰。因为登山家在一个山峰上，所以无法马上向上爬——为了到达一个海拔更高的地点，登山家需要先下山才能上山。下山的路不及上山精彩，因此，登山家想将从当前地点到达更高山峰途中最低点的海拔最大化。

例如，如果岛屿的轮廓如图中所示，并且登山家在海拔为E4的山峰，那么有三个山峰有更高的海拔（E5,E6和E7），但是路途中最低点最高的路径是到达海拔E7的山峰的路径——在路上他不会走到海拔E2以下（在其他路径中他必须经过海拔E1的地点）。如果他从海拔E5的山峰出发，那么对应路径经过的最低海拔为E3（到达E6的路径），但是如果他从E6 出发，那么最低点就是E1。

岛屿的地图是一个二维的N*M的矩形网格，并且描述了岛屿每一部分的海拔——格子里的数字表示岛屿对应地区的海拔。如果两个各自有公共点，那么他们相邻。因此，每个格子（除了在边界上的）和其他8个格子相邻。一条路径是一系列的格子，序列中连续的两个格子相邻。一个“平区域”是一个相同海拔格子的集合，并且集合中任意两个格子能够用仅经过这个集合内格子的路径连接。任意两个等高的相邻格子属于同一“平区域” 。一座山峰，是一个相邻的格子中没有更高海拔的“平区域”。

写一个程序，找到所有山峰，并且计算每个山峰到达更高山峰路途中最大的最低海拔。对于岛上最高的山峰（岛上没有更高的山峰），可以确定登山家会离开岛屿寻找更高的山峰，因此，路途中的最低海拔为零（海平面的海拔）。

1<=N,M<=2000，N∗M<=105,1<=Eij<=106

(⊙ ▽ ⊙)

先把网格按高度从大到小排序， 然后依次插入网格。

每次插入网格 C 后，询问其相邻的网格； 若其相邻的网格存在已被访问过的，那么这个网格所在的“平区域”肯定不是峰； 同时可以更新其相邻的网格所在的峰的答案。

否则C就是峰。

---

细节很多，特判很多，出题人是SB。

(￣～￣)

#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #define ll long long #define pos(x,y) (((x)-1)*m+(y)) using namespace std; const char* fin="peaks.in"; const char* fout="peaks.out"; const int inf=0x7fffffff; const int maxn=100007,maxm=2006; const int f[8][2]={{0,1},{1,1},{1,0},{-1,0},{-1,-1},{0,-1},{1,-1},{-1,1}}; int n,m,i,j,k,tot,xx; int a[maxm][maxm],rf[maxm][maxm],go[maxm*maxm],Rf[maxm*maxm]; bool bz[maxm][maxm]; int dad[maxn]; int ans1; struct node{ int x,y,z,ans; int feng; }b[maxn],ans[maxn]; bool cmp(const node &a,const node &b){ return a.z>b.z || (a.z==b.z && a.x<b.x) || (a.z==b.z && a.x==b.x && a.y<b.y); } bool cmp1(node a,node b){ return a.feng>b.feng || (a.feng==b.feng && a.z>b.z) || (a.feng==b.feng && a.z==b.z && a.ans>b.ans); } bool cmp2(node a,node b){ return a.x>b.x || (a.x==b.x && a.y>b.y); } int getdad(int v){ if (!dad[v]) return v; dad[v]=getdad(dad[v]); return dad[v]; } int getgo(int v){ if (!go[v]) return v; go[v]=getgo(go[v]); return go[v]; } void merge(int v,int u){ int j=getdad(v),k=getdad(u); dad[j]=k; } int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d%d",&n,&m); k=0; for (i=1;i<=n;i++) for (j=1;j<=m;j++){ scanf("%d",&a[i][j]); b[++tot].x=i; b[tot].y=j; b[tot].z=a[i][j]; } sort(b+1,b+tot+1,cmp); for (i=1;i<=tot;i++) rf[b[i].x][b[i].y]=i; for (i=1;i<=tot;i++){ b[i].feng=1; for (j=0;j<8;j++){ int X=b[i].x+f[j][0],Y=b[i].y+f[j][1]; if (X>0 && X<=n && Y>0 && Y<=m){ if (bz[X][Y]){ b[i].feng=0; int tmp=getdad(rf[b[i].x][b[i].y]); int tmd=getdad(rf[X][Y]); if (b[tmp].z>b[tmd].z){ if (tmp!=tmd){ dad[tmd]=tmp; b[tmd].ans=max(b[tmd].ans,b[i].z); } }else{ if (tmp!=tmd){ dad[tmp]=tmd; if (b[tmp].z!=b[tmd].z){ b[tmp].ans=max(b[tmp].ans,b[i].z); }else{ if (b[i].z==b[tmp].z) b[tmp].feng=0; go[pos(b[tmp].x,b[tmp].y)]=pos(b[tmd].x,b[tmd].y); } } } } } } bz[b[i].x][b[i].y]=true; } sort(b+1,b+tot+1,cmp1); for (i=1;i<=tot;i++) Rf[pos(b[i].x,b[i].y)]=i; for (i=1;i<=tot;i++){ if (!b[i].feng) break; if (b[i].z==b[Rf[getgo(pos(b[i].x,b[i].y))]].ans){ continue; } ans1++; ans[ans1].x=b[i].z; ans[ans1].y=b[Rf[getgo(pos(b[i].x,b[i].y))]].ans; } sort(ans+1,ans+ans1+1,cmp2); printf("%d\n",ans1); for (i=1;i<=ans1;i++) printf("%d %d\n",ans[i].x,ans[i].y); return 0; }

(⊙v⊙)

关键点： 1.把网格按高度从大到小排序 由于要求最小值的最大值，又可以通过单个网格来更新答案； 所以可以采用排序的方法。