jiguangxuanying.cpp

ACM HDOJ http://acm.hdu.edu.cn/showproblem.php?pid=1052

#include <stdlib.h> 
#include <stdio.h> 

int thorse[1001], khorse[1001], tag[1001], start1, start2, horses; 

int cmpasc(const void * A, const void * B) 
{ 
   return (*(int*)A-*(int*)B); 
} 

int main() 
{ 
   int n, i, j, total, sub; 
   while(scanf("%d", &n)!=EOF) 
   { 
      if(n==0)break; 
      for(i=0;i<n;++i) scanf("%d", &thorse[i]); 
      for(i=0;i<n;++i) scanf("%d", &khorse[i]); 
      for(i=0;i<n;++i) tag[i] = 1; 
      qsort(thorse, n, sizeof(int), cmpasc); 
      qsort(khorse, n, sizeof(int), cmpasc); 
      start1 = start2 = total = 0; 
      horses = n; 
      while(horses > 0)
      { 
            // 统计并去除绝对会输的
         for(i = start1; i< horses + start1; ++i)
			 if(thorse[i] >= khorse[start2])
				 break; 
         total -= i - start1; horses -= i - start1; start1 = i; 
         for(i = start2; i< horses + start2; ++i) 
			 if(khorse[i] >= thorse[start1])
				 break; 
         total += i - start2; start1 = start1 + i - start2; horses -= i - start2; start2 = i; 
         // 统计并去除绝对会赢的 
         for(i = start1 + horses - 1; i >= start1; --i)
			 if(thorse[i] <= khorse[start2 + horses - 1])
				 break; 
         total += start1 + horses - i - 1; horses -= start1 + horses - i - 1; 
         for(i = start2 + horses - 1; i >= start2; --i)
			 if(khorse[i] <= thorse[start1 + horses - 1])
				 break; 
         total -= start2 + horses - i - 1; start1 += start2 + horses - i - 1; horses -= start2 + horses - i - 1; 
         // 出现最大和最小速度都相等的 
         if(thorse[start1]==khorse[start2]&&thorse[start1+horses-1]==khorse[start2+horses-1]) 
         {    
            if(thorse[start1]<khorse[start2+horses-1]) total--; 
            start1++; 
            horses--; 
         } 
      } 
      printf("%d\n", total * 200); 
   } 
   return 1; 
}