#include<stdio.h>
#include<string.h>
void QSort(int low,int high);
int Partition(int low,int high);

struct clothes
{
  int num;
  int tf;
  char col[10];
};
int temp[100],total;

void main()
{
int i,j,M,N,k,p,s1,s2;
char color[10][10];
struct clothes c[100];
//FILE * file = freopen("a.txt","r",stdin);
while(scanf("%d %d",&M,&N)>0)
{
  if(M==0&&N==0)break;
  for(i=0;i<M;i++)
    scanf("%s",color[i]);
   for(j=0;j<N;j++)
   {
    scanf("%d %s",&c[j].num,c[j].col);
	c[j].tf=1;
   }
   for(total=j=0;j<N;j++)
   {
	 if(!c[j].tf)continue;
	 k=0;
	 s1=s2=0;
     temp[k]=c[j].num;
	 c[j].tf=0;
     for(i=0;i<N;i++)
	 {
       if(!c[i].tf)continue;
       if(!strcmp(c[j].col,c[i].col)){temp[++k]=c[i].num;c[i].tf=0;}
	 }
     //printf("\n%d----------1\n",j);
	 //for(p=0;p<=k;++p)printf("%d^",temp[p]);
     //printf("\n%d----------2\n",j);
     QSort(0,k);
     //for(p=0;p<=k;++p)printf("%d^",temp[p]);
     //printf("\n*************\n");
	 if(k==1||k==0)total=total+temp[k];
	 else
	 {
	 for(i=k,s1=temp[i--];i>=0;--i)
	 {
		 if(s1<s2)s1=s1+temp[i];
		 else s2=s2+temp[i];
	 }
	 if(s2<s1)s2=s1;
	 total=total+s2;
	 }
   }
   printf("%d\n",total);
}
//fclose(file); 
}

void QSort(int low,int high)
{
		if(low<high)
		{
			int j=Partition(low,high);
			QSort(low,j-1);
			QSort(j+1,high);
		}
}
		
int Partition(int low,int high)
{
		int pivotkey=temp[low];
		while(low<high)
		{
			while(low<high&&temp[high]>=pivotkey)--high;
			temp[low]=temp[high];
			while(low<high&&temp[low]<=pivotkey)++low;
			temp[high]=temp[low];
		}
		temp[low]=pivotkey;
		return low;
}

• Re:请帮我看看这种做法问题出在哪里,我已经做了一晚了,就是不能AC,晕死了!! (340) sosoquan 2007-04-05 13:04:32
  • Re:请帮我看看这种做法问题出在哪里,我已经做了一晚了,就是不能AC,晕死了!! (33) yns0501 2007-04-05 19:54:02
    • Re:请帮我看看这种做法问题出在哪里,我已经做了一晚了,就是不能AC,晕死了!! (54) wpolly 2007-04-07 02:37:59