HA2795Billboard 可用線段樹

#include<iostream>using namespace std;#include<cstdio>#include<algorithm>#define maxn 200005int h,n,w;int root[maxn<<4];int ans;//標記void make_tree(int l,int r,int rt){if(l==r){root[rt]=w;return ;}int mid=(r+l)/2;make_tree(l,mid,rt*2);make_tree(mid+1,r,rt*2+1);root[rt]=max(root[rt*2],root[rt*2+1]);}void query(int b,int l,int r,int rt){if(root[rt]<b)return ;if(l==r){root[rt]-=b;ans=l;return;}int mid=(l+r)/2;if(ans==-1) query(b,l,mid,rt*2);if(ans==-1) query(b,mid+1,r,rt*2+1);if(ans!=-1) root[rt]=max(root[rt*2],root[rt*2+1]);}int main(){while(scanf("%d%d%d",&h,&w,&n)!=EOF){if(h>200000) h=200000;make_tree(1,h,1);while(n--){int a;ans=-1;scanf("%d",&a);query(a,1,h,1);printf("%d\n",ans);}}return 0;}

?

第一眼又是坑長的英文,細看外加用了點靈格斯，題目大意是一個廣告欄要加廣告上去，輸入廣告欄的長(h)寬(w)和所加廣告的個數n，然后n行依次輸入n個數代表所加廣告的寬（廣告的長都是1），每一次加廣告上去，都盡量把廣告往左上位置放，每放一個廣告輸出它放在廣告欄的第幾行（長度），沒有位置放則輸出"-1"。

?????用線段樹，建樹，每一個root[rt]=w,放廣告就從左樹先查找，長度從小到大，當滿足root[rt]>n[i]能放廣告時，記下left位置，并相應的減去x[i]，輸出left;不能放輸出"-1"。