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;
}