poj 2380

题意：这道题想了很久很久才理解题意。题目描述很简单，就是给出几组数据，分别表示商品的id号，商品的销售点，以及商品在销售点的销售额。目的要求你给出一个数组，其中数组的首行按照商品的id号从小到大排列，首列按照商品的销售点从小到大排列，数组里面的值代表某件商品在某个销售点的销售额。

思路分析：刚开始考到这个题目的时候，觉得无从下手，结果思考一下，发现这个也仅仅是个排序题而已。只需要将商品的id号升序排列，商品的销售点升序排列，然后按照题目要求的方式输出结果即可。但是，分析的时候，发现数据范围是在太大了，上上下下，任何一个方向的不算很坏的情况都有可能超时，而且数据的值也很大，哈希是不可能用的，所以要高效的解决这个问题，就得时时小心，把排序和比较的效率尽量提高。看了这道题提交的情况，就发现这题应该属于难题，主要是数据量加大了难度,写完百度一下，发现都没什么人发解题报。考虑到效率问题最后决定用vector来解决的数据量大的问题，虽然会损失效率。然后用快排先对商店排序，在同一个商店内对item的id排序，因为开头要先输出一行item的id，所以需要先记录下item的id号，于是我用插入排序和二分查找的方法来得到最终获取所有的item的id号，因为考虑到item的id号如果乱的话，查找id是否存在所花费的代价会比较大，所以采用了二分查找，而二分查找要求序列是有序的，既然序列有序，那么插入一个不存在的的id的话，用插入排序就行了。得到排好的序列后，就成了一个标记和输出的问题，值得注意的是，每次在标记新的qi的时候，都要把该商店内没有的id先填为0，也就是移到对应的qi的位置。代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
	int qi,si,vi;
};
vector<node> data;
int item[300010],len=0;
int cmp(const void* e1,const void* e2)
{
	node* a=(node*)e1;
	node* b=(node*)e2;
	if(a->si>b->si)
		return 1;
	if(a->si==b->si)
		return a->qi-b->qi;
	return -1;
}
bool isitemexit(int a)//id是否存在
{
	if(len==0)
		return false;
	int start=0,end=len-1,q;
	while(end>=start)
	{
		q=(start+end)/2;
		if(item[q]==a)
			return true;
		if(item[q]>a)
			end=q-1;
		else
			start=q+1;
	}
	return false;
}
void insert_sort()
{
	int i;
	for(i=len-1;i>=1;--i)
	{
		if(item[i]>item[i-1])
			return;
		int temp=item[i];
		item[i]=item[i-1];
		item[i-1]=temp;
	}
}
void printzero(int n)
{
	int i;
	for(i=n;i<len;++i)
		printf(" 0");
	printf("\n");
}
int main()
{
	int n,i,pre_si,pre_qi,pre_vi,j;
	scanf("%d",&n);
	for(i=0;i<n;++i)
	{
		node temp;
		scanf("%d %d %d",&temp.qi,&temp.si,&temp.vi);//输入id号，销售点，以及销售的数量
		data.push_back(temp);//数据进入数据库
		if(!isitemexit(temp.qi))//检测是否存在相同的id号,典型的二分查找方法
		{
			item[len++]=temp.qi;
			insert_sort();//插入id号
		}
	}
	qsort(&(data[0]),data.size(),sizeof(node),cmp);//先对si号进行升序排列，如果si号相同，则按照qi的升序进行排列
	
	node temp;
	temp.si=-1;
	data.push_back(temp);
	printf("-1");
	for(i=0;i<len;++i)
		printf(" %d",item[i]);
	printf("\n");
	pre_si=data[0].si;
	pre_qi=data[0].qi;
	pre_vi=0;
	j=0;
	printf("%d",pre_si);
	while(item[j]!=pre_qi)
	{
		printf(" 0");
		j++;
	}
	for(i=0;i<data.size();i++)
	{
		int m;
		m=data[i].si;
		if(pre_si!=data[i].si)
		{
			printf(" %d",pre_vi);
			printzero(j+1);//输出零操作
			if(i==data.size()-1)
				break;
			printf("%d",data[i].si);
			pre_si=data[i].si;
			pre_qi=data[i].qi;
			pre_vi=0;
			j=0;
			while(item[j]!=pre_qi)
			{
				printf(" 0");
				j++;
			}
		}
		if(pre_qi!=data[i].qi)
		{
			
			printf(" %d",pre_vi);
			pre_qi=data[i].qi;
			j++;
			while(item[j]!=pre_qi)
			{
				printf(" 0");
				j++;
			}
			pre_vi=0;
		}
		pre_vi+=data[i].vi;
	}
	return 0;
}