1763.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
#include"algorithm"
using namespace std;
long x[260000],y[260000];
long ordx[260000],ordy[260000];
inline long abs(long a)
{return a>0?a:-a;}

int cmpx(long a,long b)
{return x[a]<x[b]||(x[a]==x[b]&&y[a]<y[b]);}
int cmpy(long a,long b)
{return y[a]<y[b]||(y[a]==y[b]&&x[a]<x[b]);}

int main()
{char c;long xn,yn,n,i,bb,eb,lb,b,e,l;
cin>>n;	
xn=0;yn=0;ordx[0]=0;ordy[0]=0;x[0]=0;y[0]=0;

for(i=1;i<=n;i++)
{cin>>c;
	switch(c)
	{case'N':yn--;break;
	 case'S':yn++;break;
	 case'W':xn--;break;
	 case'E':xn++;break;
	 default:break;
	}
 x[i]=xn;y[i]=yn;ordx[i]=i;ordy[i]=i;
}

sort(&ordx[0],&ordx[n+1],cmpx);
sort(&ordy[0],&ordy[n+1],cmpy);
lb=99999999;

for(i=1;i<=n;i++)
if(x[ordx[i]]==x[ordx[i-1]])
	{b=ordx[i]<ordx[i-1]?ordx[i]:ordx[i-1];
	 e=ordx[i]>ordx[i-1]?ordx[i]:ordx[i-1];
	 l=y[ordx[i]]-y[ordx[i-1]];
	 if((e-b)!=l)
	 {if(l<lb){lb=l;bb=b;eb=e;}
	  else if(l==lb){if(b<bb){bb=b;eb=e;}
	 		 else if(b==bb){if(e>eb)eb=e;}
	  		}
       	 }
	}
for(i=1;i<=n;i++)
if(y[ordy[i]]==y[ordy[i-1]])
    {b=ordy[i]<ordy[i-1]?ordy[i]:ordy[i-1];
     e=ordy[i]>ordy[i-1]?ordy[i]:ordy[i-1];
     l=x[ordy[i]]-x[ordy[i-1]];
     if((e-b)!=l)
      {if(l<lb){lb=l;bb=b;eb=e;}
       else if(l==lb){if(b<bb){bb=b;eb=e;}
                      else if(b==bb){if(e>eb)eb=e;}
                      }
       }
     }

cout<<lb<<' '<<bb<<' '<<eb<<' ';
if(x[bb]==x[eb])
{if(y[eb]>y[bb])cout<<'S';
	 else cout<<'N';
}
if(y[bb]==y[eb])
{if(x[eb]>x[bb])cout<<'E';
         else cout<<'W';
}
cout<<endl;
return 0;
}