房子投影 堆.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
//NOJ 房子投影 堆结构 
/*
4
1 4 3
2 7 2
6 9 4
9 10 3

6
1 5 10
3 8 8
4 7 20
8 9 40
10 14 30
12 13 15

输出
28
258
*/

typedef struct xhigh
{
	__int64 x;//高度的横坐标
	__int64 y;//高度的纵坐标
	bool add;//是房子的左竖线还是右竖线
	__int64 hhouse;//对应哪一个房子
}xhigh;

#define NMAX 85000
__int64 house[NMAX];//house[i],i房子的左竖线在heap中的下标
__int64 heap[NMAX];//高度优先堆
__int64 heaphou[NMAX];//heaphou[i],堆[i]的竖线对应哪个房子
xhigh shuru[NMAX*2];
xhigh chuli[NMAX*2];

void insert_heap(__int64 high,__int64 num,__int64 newhou)
{//把高度high插入到heap[1..num-1]中,高度high对应编号为newhou的房子
	__int64 rc,j;
	heap[num]=rc=high;
	for(j=num/2;j>=1;j/=2)
	{
		if(heap[j]<rc) 
		{
			heap[num]=heap[j];
			heaphou[num]=heaphou[j];
			house[heaphou[num]]=num;
		}
		else break;
		num=j;
	}
	heap[num]=rc;
	heaphou[num]=newhou;
	house[heaphou[num]]=num;
}

void delete_heap(__int64 delenum,__int64 num)
{//将heap[1..num]中编号为delenum的元素删除
	__int64 temp,j,temphou,rc,start;
	//先将要删除的元素和堆尾元素调换位置,然后删除堆尾元素
	//注意heaphou[],和house也要修改
	temp=heap[num];heap[num]=heap[delenum];heap[delenum]=temp;
	temphou=heaphou[num];
	heaphou[num]=heaphou[delenum];
	heaphou[delenum]=temphou;
	house[heaphou[delenum]]=delenum;
	house[heaphou[num]]=num;
	heap[num]=0;//把堆尾元素给sm掉了
	rc=heap[delenum];
	start=delenum;
	if((delenum*2<num&&heap[delenum]<heap[delenum*2])||(
		delenum*2+1<num&&heap[delenum]<heap[delenum*2+1]))
	{//向下调整
		for(j=delenum*2;j<num;j*=2)
		{
			if(j<num-1&&heap[j]<heap[j+1]) j++;
			if(rc>heap[j]) break;
			heap[delenum]=heap[j];heaphou[delenum]=heaphou[j];
			house[heaphou[delenum]]=delenum;
			delenum=j;
		}
		heap[delenum]=rc;
		heaphou[delenum]=temphou;
		house[heaphou[delenum]]=delenum;
	}
	delenum=start;
	rc=heap[delenum];
	if(delenum/2>=1&&heap[delenum/2]<heap[delenum])
	{//向上调整
		for(j=delenum/2;j>=1;j/=2)
		{
			if(rc<heap[j]) break;
			heap[delenum]=heap[j];
			heaphou[delenum]=heaphou[j];
			house[heaphou[delenum]]=delenum;
			delenum=j;
		}
		heap[delenum]=rc;
		heaphou[delenum]=temphou;
		house[heaphou[delenum]]=delenum;
	}
}

bool cmpx(struct xhigh a,struct xhigh b)
{
	//注意排序的原则：
	//横坐标小的在前，横坐标一样的，左竖线在前（靠，不然会删除未出现的竖线）
	return a.x<b.x||(a.x==b.x&&a.add==true&&b.add==false);
}

__int64 solve(int num)
{
	__int64 i,lastx,sql=0,heapnum,ss;
	for(i=1;i<=2*num;i++)
		chuli[i]=shuru[i];
	sort(chuli+1,chuli+1+num*2,cmpx);
	lastx=chuli[1].x;
	heapnum=0;
	for(i=1;i<=2*num;i++)
	{
		ss=(chuli[i].x-lastx)*heap[1];
		sql+=ss;
		if(chuli[i].add==true)
		{	//左竖线
			heapnum++;
			insert_heap(chuli[i].y ,heapnum,chuli[i].hhouse); 
		}
		else
		{	//右竖线
			delete_heap(house[chuli[i].hhouse],heapnum);
			heapnum--;
		}
		lastx=chuli[i].x;//不解释。。。
	}
	return sql;
}
int main()
{
	__int64 num,i,ta,tb,th,j;
	while(scanf("%I64d",&num)!=EOF)
	{
		for(i=1,j=1;i<=num;i++)
		{
			scanf("%I64d%I64d%I64d",&ta,&tb,&th);
			shuru[j].x=ta;
			shuru[j].y=th;
			shuru[j].add=true;
			shuru[j].hhouse=i;
			j++;
			shuru[j].x=tb;
			shuru[j].y=th;
			shuru[j].add=false;
			shuru[j].hhouse=i;
			j++;
		}
		printf("%I64d\n",solve(num));
	}
	return 0;
}