题目链接~~>
做题感悟：这题主要是想到以什么为线段树的叶子节点就好解决了。
解题思路：
读完题，你会发现 h , w 的范围都很大，如果把他们作为线段树的叶子节点的话肯定是不行的，再一看 n ,貌似可以把他作为叶子节点，这样的话每个叶子节点代表一行，在选择的时候只要尽量选择左子树上的大于海报长度的就可以，这样的话，区间保存的就是最大值，如果最大值都比当前的报纸小 必定不会继续往下搜了。
代码：
?
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std ; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const int mod = 1e9 + 7 ; const int MY = 50000 + 5 ; const int MX = 200000 + 5 ; int n ,h ,w ; struct node { int le ,rt ,c ; }T[MX*4] ; void build(int x ,int le ,int rt ,int w) { T[x].le = le ; T[x].rt = rt ; T[x].c = w ; if(le == rt) return ; int Mid = (le + rt)>>1 ; build(L(x) ,le ,Mid ,w) ; build(R(x) ,Mid+1 ,rt ,w) ; T[x].c = w ; } int Query(int x ,int w) // 查询同时修改最大值 { if(T[x].c < w) return -1 ; if(T[x].le == T[x].rt) { T[x].c = T[x].c - w ; return T[x].le ; // 返回找到的点 } int mx = -1 ; if(T[L(x)].c >= w) mx = Query(L(x) ,w) ; else if(T[R(x)].c >= w) mx = Query(R(x) ,w) ; T[x].c = max(T[L(x)].c ,T[R(x)].c) ; return mx ; } int main() { //freopen("input.txt" ,"r" ,stdin) ; int x ; while(~scanf("%d%d%d" ,&h ,&w ,&n)) { int nx = n ; if(h < n) n = h ; // 可以优化一下 build(1 ,1 ,n ,w) ; for(int i = 0 ;i < nx ; ++i) { scanf("%d" ,&x) ; printf("%d\n" ,Query(1 ,x)) ; } } return 0 ; }