#include<stdio.h>
#include<memory.h>
#define  inf   1<<28
#define  maxN  50005
int main()
{ 
  int  i,j,k,n,m,index,nCount;
  int  min,max,minl,minr;
  bool  v[maxN];
  int   d[maxN]; // 记录被destroy的village位置
  char   m_Event;
  index = 0;     // 被destroy的village数目
  memset(v,0,sizeof(v));
  memset(d,0,sizeof(d));
  scanf("%d%d",&n,&m); // n: village数目 
  for(i=0;i<m;i++)
  {
	 scanf(" %c ",&m_Event);
	 switch(m_Event)
	 {
	  case 'D':
          scanf("%d",&k); // 事件位置
		  if( v[k] == 0)
		  { 
			  v[k] = 1;  
		      d[index++] = k;
		  }
          break;
	  case 'Q':
          scanf("%d",&k); // 事件位置
		  nCount = 0;
		  if(v[k]==0)
		  {
		   if(index)
		   {
			min  = inf;
			max  = 0;
		    minl = inf;
			minr = inf;
		    for(j=0;j<index;j++)
			{
				if(d[j]>max)
					max = d[j];
				if(d[j]<min)
					min = d[j];
				if(d[j] - k>0 && d[j] - k<minr)
				   minr = d[j] - k;
				if(d[j] - k<0 && k - d[j]<minl)
				   minl = k - d[j];
			}
			if(minl == inf)
		        nCount = min - 1;
			else if(minr == inf)
				nCount = n - max;
			else
				nCount = minl + minr - 1;
		   }
		   else
			   nCount = n;
		  }
		  printf("%d\n",nCount);
		  break;
	  case 'R':
		  if(index>0)
             v[d[--index]] = 0;
	      break;
	  default:
		  break;
	 }
  }
  return 0;
}

• Re:想不通,怎么超时的,哪位帮看看 (33) swust20115290 2012-08-11 10:08:25
  • Re:想不通,怎么超时的,哪位帮看看 (20) 476313260 2013-10-09 14:15:47