这道题谁AC了，我的老是TLE，帮忙看看，
代码：

#include<stdio.h>

typedef struct
{
	int qi; //item的id
	int si; //销售点的id
	int vi; //销售的数量 
} log;

log data[500000]; //保存输入的数据 
int head[10000]; //保存从第2列开始的表头 
int row[10000];  //保存从第2列开始的一行数据 

int cmp_qi(const void *a, const void *b)
{
	return ((log*)a)->qi - ((log*)b)->qi;
}

int cmp_si(const void *a, const void *b)
{
	return ((log*)a)->si - ((log*)b)->si;
}

//搜索qi在head数组中的下标 
int search(int qi, int n)
{
	int i,j,mid;
	i=0; 
	j=n-1;
	mid=(i+j)>>1;
	while(head[mid] != qi)
	{
		if(qi < head[mid]) j=mid-1;
		else i=mid+1;
		mid=(i+j)>>1;
	}
	return mid;
}

void print_row(int colsnum, int si)
{
	int i;
	printf("%d", si);
	for(i=0; i<colsnum; i++) {printf(" %d", row[i]); row[i]=0;}
	printf("\n");
}

int main()
{
	int n,i,j,last,colsnum;
	scanf("%d", &n);
	for(i=0; i<n; i++) scanf("%d %d %d", &data[i].qi, &data[i].si, &data[i].vi);
	
	//按qi排序
	qsort(data, n, sizeof(log), cmp_qi);
	//统计有多少个不同的qi，并保存到head数组
	colsnum=0;
	last=-1;
	for(i=0; i<n; i++)
	{
		if(data[i].qi != last)//新的qi 
		{
			last=data[i].qi;
			head[colsnum++]=data[i].qi;
		}
	}
	//输出表头
	printf("%d", -1);
	for(i=0; i<colsnum; i++) printf(" %d", head[i]);
	printf("\n");
	
	//按si排序
	qsort(data, n, sizeof(log) , cmp_si);
	//统计每个销售点每个物品的销售量，并输出
	last=data[0].si;
	for(i=0; i<n; i++)
	{
		if(data[i].si != last) //上一个销售点统计完毕，输出结果 
		{
			print_row(colsnum, last);
		}
		
	  last=data[i].si;
	  
		//找出当前log中qi在head数组中的下标
		j= search(data[i].qi, colsnum);
		//row数组中对应的cell值加vi
		row[j] += data[i].vi;
	}
	//输出最后一行
	print_row(colsnum, last);
	
	return 0;
}

• Re:2380 Sales Report大数据量处理，老是TLE，有没有好的算法 (16) yinbenli 2012-04-24 18:42:59
  • Re:sjckd (18) yinbenli 2012-04-24 18:43:18