1895740_ac_1562ms_72k.c

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

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

typedef struct node
{
	long big;
	struct node *next;
}B;
B *top1, *p1, *q1;
typedef struct Node
{
	long small;
	struct Node *next;
}S;
S *top2, *p2, *q2;
int main()
{
	int n1, n2, mark1, mark2;
	long i, n, tmp;
	double sum;

	top1 = (B *)malloc(sizeof(B));
	top2 = (S *)malloc(sizeof(S));
	top1->next = NULL; 
	top2->next = NULL;

	while(scanf("%d%d%ld",&n1,&n2,&n)==3&&n1&&n2&&n)
	{
		sum = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%ld",&tmp);
			sum+=tmp*1.0/(n-n1-n2);
			mark1 = mark2 = 0;
			if(i < n1)
				mark1 = 1;
			else if(tmp > top1->next->big)
				mark1 = 2;
			if(i < n2)
				mark2 = 1;
			else if(tmp < top2->next->small)
				mark2 = 2;
			if(mark1)
			{
				p1 = (B *)malloc(sizeof(B));
				p1->big = tmp;
				q1 = top1;
				while(q1->next)
				{
					if(q1->next->big > p1->big)
						break;
					else
						q1 = q1->next;
				}
				p1->next = q1->next;
				q1->next = p1;
				if(mark1==2)
				{
					q1=top1->next;
					top1->next=top1->next->next;
					free(q1);
				}
			}
			if(mark2)
			{
				p2 = (S *)malloc(sizeof(S));
				p2->small= tmp;
				q2 = top2;
				while(q2->next)
				{
					if(q2->next->small < p2->small)
						break;
					else
						q2 = q2->next;
				}
				p2->next = q2->next;
				q2->next = p2;
				if(mark2==2)
				{
					q2=top2->next;
					top2->next=top2->next->next;
					free(q2);
				}
			}
		}
		p1 = top1;
		while(p1->next)
		{
			q1 = p1->next;
		    sum-=p1->next->big*1.0/(n-n1-n2);
		    p1->next = p1->next->next;
			free(q1);
		}
		p2 = top2;
		while(p2->next)
		{
			q2 = p2->next;
		    sum-=p2->next->small*1.0/(n-n1-n2);
		    p2->next = p2->next->next;
			free(q2);
		}
		printf("%lf\n",sum);
	}
	return 1;
}