首页 > 代码库 > HDU 2795 Billboard

HDU 2795 Billboard

单点更新,h>n时直接取h=n即可,初始每个数为w,每次找出从左网友第一个大于当前的位置输出并更新

 

#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>#include<vector>#include <iostream>#define debug(x) printf(#x"= %d\n",x);#define N 200050#define max(x,y) ((x)>(y)?(x):(y))using namespace std;int value[N*4];int w[N];void build(int l,int r,int i){    if(l==r)    {        value[i]=w[l];        return;    }    int mid=(l+r)>>1;    build(l,mid,i<<1);    build(mid+1,r,i<<1|1);    value[i]=max(value[i<<1],value[i<<1|1]);}void update(int l,int r,int p,int va,int i){    if(l==r)    {        value[i]=va;        return;    }    int mid=(l+r)>>1;    if(p<=mid)update(l,mid,p,va,i<<1);    else update(mid+1,r,p,va,i<<1|1);    value[i]=max(value[i<<1],value[i<<1|1]);}int query(int l,int r,int va,int i){    if(l==r)        return l;    int mid=(l+r)>>1;    if(value[i<<1]>=va)return query(l,mid,va,i<<1);    else return query(mid+1,r,va,i<<1|1);}int n,W,H;void init(){    for(int i=1;i<=H;++i)        w[i]=W;    build(1,H,1);}void solve(){    for(int i=0;i<n;++i)    {        int x;        scanf("%d",&x);        if(value[1]<x)            puts("-1");        else        {            int pos=query(1,H,x,1);            printf("%d\n",pos);            w[pos]-=x;            update(1,H,pos,w[pos],1);        }    }}int main() {    while(scanf("%d%d%d",&H,&W,&n)!=EOF)    {        if(H>n)H=n;        init();        solve();    }    return 0;}