链接:http://acm.hdu.edu.cn/showproblem.php?pid=2795
题意:在一块高h,宽w的木板上贴广告,广告高为1,宽为wi,每次都从最左上方贴,没位置再向下挪。按顺序输入广告宽度,输出它所在的行数,贴不下输出-1。
思路:这道题一开始看不出来是线段树,但是如果把木板转90°,就是一个很明显的线段树了,把原来的高度当作线段树的宽度,然后维护原来的宽度,更新直接在查询中处理
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 200010 #define eps 1e-7 #define INF 0x7FFFFFFF #define ff sqrt(5.0) typedef long long ll; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int w,h; int sum[MAXN<<2]; void PushUP(int rt){ sum[rt] = max(sum[rt<<1],sum[rt<<1|1]); } void build(int l,int r,int rt){ sum[rt] = w; if(l==r) return ; int m = (l + r) >> 1; build(lson); build(rson); } //void update(int p,int l,int r,int rt){ // if(l==r){ // sum[rt] ++; // return ; // } // int m = (l + r) >> 1; // if(p<=m) update(p,lson); // else update(p,rson); // PushUP(rt); //} int query(int x,int l,int r,int rt){ if(l==r){ sum[rt] -= x; return l; } int m = (l + r) >> 1; int ret ; if(sum[rt<<1]>=x) ret = query(x,lson); else ret = query(x,rson); PushUP(rt); return ret; } int main(){ int n,m,i,a,b; while(scanf("%d%d%d",&h,&w,&n)!=EOF){ int nn = min(h,n); build(1,nn,1); for(i=0;i<n;i++){ scanf("%d",&m); if(sum[1]<m) puts("-1"); else printf("%d\n",query(m,1,nn,1)); } } return 0; }