2380.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 500003
typedef struct
{
	long q,s,v;
}data;
data a[NMAX];
data b[NMAX];
long y[NMAX];
long x[NMAX];
long N;
int cmp(const void *a,const void *b)
{
	if(((data*)a)->s==((data*)b)->s)
		return ((data*)a)->q-((data*)b)->q;
	else
		return ((data*)a)->s-((data*)b)->s;
}
int cmp2(const void *a,const void *b)
{
	if(((data*)a)->q==((data*)b)->q)
		return ((data*)a)->s-((data*)b)->s;
	else
		return ((data*)a)->q-((data*)b)->q;
}
void solve()
{
	int i,j,k,nmax,ymax,xmax;
	qsort(a,N,sizeof(data),cmp);
	y[0]=a[0].s;
	
	j=0;
	b[0].s=a[0].s;
	b[0].q=a[0].q;
	b[0].v+=a[0].v;
	k=0;
	for(i=1;i<N;i++)
	{
		if(a[i].s==a[i-1].s&&a[i].q==a[i-1].q)
		{
			b[j].s=a[i].s;
			b[j].q=a[i].q;
			b[j].v+=a[i].v;
		}
		else
		{
			j++;
			b[j].s=a[i].s;
			b[j].q=a[i].q;
			b[j].v+=a[i].v;
		}
		if(a[i].s>y[k])
		{
			y[++k]=a[i].s;
		}
	}
	ymax=k+1;
	nmax=j+1;
	qsort(b,nmax,sizeof(data),cmp2);
	x[0]=b[0].q;
	k=0;
	for(i=1;i<nmax;i++)
	{
		if(b[i].q>x[k])
			x[++k]=b[i].q;
	}
	xmax=k+1;
	qsort(b,nmax,sizeof(data),cmp);

	
	printf("-1 ");
	for(i=0;i<xmax;i++)
	{
		printf("%d",x[i]);
		if(i<xmax-1)
			printf(" ");
		else
			printf("\n");
	}
	k=0;
	for(i=0;i<ymax;i++)
	{
		printf("%d ",y[i]);
		for(j=0;j<xmax;j++)
		{
			if(b[k].q==x[j]&&b[k].s==y[i])
				printf("%d",b[k++].v);
			else
				printf("0");
			if(j<xmax-1)
				printf(" ");
			else
				printf("\n");
		}
	}


}

int main()
{
	
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d",&N);
	long i;
	for(i=0;i<N;i++)
	{
		scanf("%d%d%d",&a[i].q,&a[i].s,&a[i].v);
	}
	
	solve();

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}