2082.txt

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

#include"set"
#include"stdio.h"
using namespace std;
struct node
{
	long heigh;
	long num;
};
struct cmp
{
	bool operator()(node a,node b)const
	{return a.heigh<b.heigh;}
};

set<node,cmp> nodes;
long hi[50010];
long x[50010];
//long long 
__int64 area[50010];
int main()
{long n,i,k,t;
node nd;
//long long
__int64  an;
set<node,cmp>::iterator iter;
while(1)
{scanf("%ld",&n);
//	cin>>n;
if(n<0)break;
nodes.clear();
nd.heigh=-1;nd.num=0;
nodes.insert(nd);
long sx=0;
x[0]=0;
for(i=1;i<=n;i++)
{
	scanf("%ld%ld",&t,&hi[i]);
//	cin>>t>>hi[i];	
	sx+=t;
	x[i]=sx;
	nd.heigh=hi[i];nd.num=i;	
iter=nodes.lower_bound(nd);
if(iter==nodes.end())area[i]=hi[i]*t;
else	area[i]=(__int64 /*long long*/)(x[nd.num]-x[iter->num-1])*hi[i];
iter=nodes.lower_bound(nd);
if(iter!=nodes.end())nd.num=iter->num;
nodes.erase(iter,nodes.end());
nodes.insert(nd);
}
an=0;
sx=0;
nodes.clear();
nd.heigh=-1;nd.num=0;
nodes.insert(nd);
for(i=n;i>0;i--)
{

	nd.heigh=hi[i];nd.num=i;
	iter=nodes.lower_bound(nd);
	if(iter!=nodes.end())area[i]+=(__int64)(x[iter->num]-x[nd.num])*hi[i];
	if(area[i]>an)an=area[i];
	iter=nodes.lower_bound(nd);
	if(iter!=nodes.end())nd.num=iter->num;
	nodes.erase(iter,nodes.end());
	nodes.insert(nd);

}
printf("%I64d\n",an);
//printf("%lld\n",an);
}
return 0;
}