2052590_tle.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
struct node
{
	char color[11];
	long num[10000];
	long p;
}cloth[10];

int N, M;

int cmp(const void *a, const void *b)
{
	return *(long *)a-*(long *)b>0?1:-1;
}

void solve()
{
	int i, j;
	long ans = 0;

	for(i = 0; i < M; i++)
	{
		if(cloth[i].p==0)
			continue;
		qsort(cloth[i].num,cloth[i].p,sizeof(cloth[i].num[0]),cmp);
		for(j = 0;;j++)
			if(cloth[i].num[j]>=(cloth[i].num[cloth[i].p-1]+1)/2)
			{
				ans+=cloth[i].num[j];
				//printf("%ld\n",cloth[i].num[j]);
				break;
			}
	}
	printf("%ld\n",ans);
}

void input()
{
	int i, j;
	long t, l, len;
	int mark[1000000];
	char tmp[11];

	while(scanf("%d%d",&M,&N)==2&&(M||N))
	{
		for(i = 0; i < M; i++)
		{
			scanf("%s",cloth[i].color);
			cloth[i].p = 0;
		}
		for(i = 0; i < N; i++)
		{
			scanf("%ld%s",&t,tmp);
			memset(mark,0,sizeof(mark));
			for(j = 0; j < M; j++)
			{
				if(strcmp(cloth[j].color,tmp)==0)
				{
					len = cloth[j].p;
					for(l = 0; l < len; l++)
						if(mark[t+cloth[j].num[l]]==0)
						{
							mark[t+cloth[j].num[l]]=1;
							cloth[j].num[cloth[j].p++] = t+cloth[j].num[l];
						}
					if(!mark[t])
						cloth[j].num[cloth[j].p++] = t;
					break;
				}
			}
		}
		solve();
	}
}

int main()
{
	input();
	return 1;
}