Posted on 2012-03-27 09:24
C小加 阅读(1067)
评论(1) 编辑 收藏 引用 所属分类:
解题报告
看了解题报告之后我在想,为什么我会傻傻的去把每一天的高度都求出来。。。。
询问哪一天就求出哪一天的高度,把天数排一下序可以在求的过程中删掉高度和增长速度都小的树。时间复杂度<=O(m*n)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXM=100003;
typedef struct
{
ll high,add;//高度和增长速度
}Tree;
Tree tree[MAXM];
ll day[MAXM];//实际的数天
ll sday[MAXM];//排序后的天数
ll ans[MAXM];//结果
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=0;i<n;++i)
{
scanf("%lld %lld",&tree[i].high,&tree[i].add);
}
for(int i=0;i<m;++i)
{
scanf("%lld",day+i);
sday[i]=day[i];
}
sort(sday,sday+m);//天数从小到大排序
memset(ans,0,sizeof(ans));
Tree tmax;
for(int i=0;i<m;++i)//枚举排序后的天数
{
tmax.high=tree[0].high+sday[i]*tree[0].add;
tmax.add=tree[0].add;
int pos=1;
for(int j=1;j<n;++j)//枚举每一颗树
{
Tree temp=tree[j];
temp.high+=sday[i]*tree[j].add;
if( !(tmax.high>=temp.high&&tmax.add>=temp.add) )//如果第j棵树在sday[i]的高度和增长速度都小于某棵树,则舍弃第j棵树
{
tree[pos++]=tree[j];
}
//找到在sday[i]时刻高度最大的树
if(tmax.high<temp.high)
{
tmax=temp;
}
}
n=pos;
ans[ sday[i] ]=tmax.high;
}
for(int i=0;i<m;++i)
printf("%lld\n",ans[ day[i] ]);
}
return 0;
}