hdoj 2795 Billboard
http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个，放在最上面（编号小） 思路：把没横行能放的最大长度看做一个序列建树。由于h比n大很多。。多出来的没用。。直接取较小值就行。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月17日 星期四 15时04分52秒
4File Name :code/hdu/2785.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E5+7;
34int h,w,n;
35
36struct SegTree //将每个横格能放置的最大长度看做一个序列，建树。
37{
38 int mx;
39}tree[4*N];
40
41void build ( int l,int r,int rt)
42{
43 // cout<<"l:"<<l<<" r:"<<r<<" rt:"<<rt<<endl;
44 tree[rt].mx = w;
45 if (l==r)
46 {
47 return ;
48 }
49 int m = (l+r)>>1;
50 build (lson);
51 build (rson);
52
53}
54
55int query( int x,int l,int r,int rt)
56{
57 if (l==r)
58 {
59 tree[rt].mx-=x; //将长度为x的改点放在第l个横格里。
60 return l;
61 }
62 int m = (l+r)>>1;
63 int res;
64 if (tree[rt<<1].mx>=x) //先搜左子树，可以保证topmost.
65 {
66 res=query(x,lson);
67 }
68 else
69 {
70 res=query(x,rson);
71 }
72
73 tree[rt].mx = max(tree[rt<<1].mx,tree[rt<<1|1].mx);
74 return res;
75}
76
77
78
79
80int main()
81{
82 #ifndef ONLINE_JUDGE
83 freopen("code/in.txt","r",stdin);
84 #endif
85
86 while (~scanf("%d %d %d",&h,&w,&n))
87 {
88 if (h>n) h = n ; //不用离散化，这样就可以。
89 build(1,h,1);
90 while (n--)
91 {
92 int x;
93 scanf("%d",&x);
94 if (x>tree[1].mx)
95 {
96 puts("-1");
97 }
98 else
99 {
100 printf("%d\n",query(x,1,h,1));
101 }
102 }
103 }
104
105 #ifndef ONLINE_JUDGE
106 fclose(stdin);
107 #endif
108 return 0;
109}