Posted on 2012-03-27 09:24
C小加 閱讀(1108)
評論(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;
}