这题我的方法是统一末尾时间
   (1)计算同一组的人中最后1个的最后时间 然后根据长短进行排序 就可以知道走的顺序
   (2)以此顺序进行重组排序 即把一组人根据之前的顺与列出先的队列
   (3)将2个队列中的没一个最后时间计算时间差再分别乘上各自人数 就可以得出节省的时间了
     我的代码没有经过优化,很繁杂 望高手们给予优化哈 时间用的有点长,相信有很大的改进空间 (个人认为比较好理解哈)!
    附上代码哦 
   #include<stdio.h>
 int a[100000],b[100000],e[100000];
 int n,i,j,c,k,l,s,h,g;
 char x,y,z[100000],d[100000]; 随便开的都开的比较大
int main()
{
 scanf("%d",&n);
 g=n;
 for(h=1;h<=g;h++)
 {
  scanf("%d",&c);
  getchar();
  s=0;
  for(i=0;i<c;i++)
  {
   scanf("%c",&z[i]);    将每个人按顺序存入z
   b[i]=0;                        清0
   a[i]=0;
  }
  k=0;
  for(i=c-1;i>=0;i–)
  {
   for(j=c-1;j>i;j–)
   {
    if(z[i]==z[j])                            从后往前找每组的最后1个人(重复跳过)
     break;
   }
   if(j==i)
   {
    a[k]=i+1;
    d[k]=z[i];
     k++;
   for(l=0;l<c;l++)
   {
    if(z[l]==d[k-1])                            计算各组的人数
     b[k-1]++;
   }
   e[k-1]=b[k-1];
   }
  }
 
  for(i=k-1;i>=0;i–)
  {
   s=s+(a[i]-e[i])*b[i]*5;                    将原队列各组最后位置与新队列的进行计算 乘上人数计算节省时间累加

    e[i-1]+=e[i];                                    
  }
  printf("%d\n",s);
 }
 return 0;
 }

发表评论

电子邮件地址不会被公开。

Post Navigation