首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。