(计蒜客) 公告板 (线段树应用)

超、凢脫俗 2022-02-19 04:43 173阅读 0赞

蒜厂有一个 h×w 的矩形公告板，其中 h 是高度，w 是宽度。  
现在有若干张 1×Wi 的公告， Wi 是宽度，公告只能横着放，即高度为 1 的边垂直于水平面，且不能互相有重叠，每张公告都要求尽可能的放在最上面的合法的位置上。  
若可以放置，输出每块可放置的位置的行号；若不存在，输出 −1。行号由上至下分别为 1,2,…,h。

输入格式  
第一行三个整数 h，w，n (1≤h,w≤10^9;1≤n≤200,000) 。  
接下来 n 行，每行一个整数 Wi(1≤Wi≤109) 。

输出格式  
输出n 行，一行一个整数。

样例输入:

3 5 5  
2  
4  
3  
3  
3  
1  
2  
3  
4  
5  
6  
样例输出

1  
2  
1  
3  
\-1

解题思路:

利用线段树,区间为h,叶子结点为每一个高度,每一个非叶子结点保存的是子结点宽度的最小值

之后遍历,只要能找到一个叶子结点插入,那么就输出这个结点的值,否则输出-1

注意输出要用scanf和printf否则会超时

#include <iostream>
    #include <algorithm>
    #include <math.h>
    #include <string.h>
    #include <stdio.h>
    using namespace std;
    const int MAXN = 1000000;
    int mMaxTree[4*MAXN];   //数组最大容量,以高度为准
    int N, M, R;
    bool flag = false;
    int curLayer = -1;
    
    void mUp(int p) {
    	mMaxTree[p] = min(mMaxTree[p * 2], mMaxTree[p * 2 + 1]);  //返回子结点中的较大值
    }
    
    void segModified(int p, int l, int r, int d) {
    	if (mMaxTree[p] + d > M || flag == true) {  //如果已经得到答案,或者超出范围
    		return;   //如果超范围,直接返回
    	}
    	if (l == r) { //遍历到叶节点了,赋值
    		if (mMaxTree[p] + d <= M) {
    			mMaxTree[p] += d;
    			curLayer = l;  //保存当前层号
    			flag = true;   
    		}
    		return;   
    	}
    	int mid = (l + r) / 2;
    	segModified(p * 2, l, mid,d);
    	segModified(p * 2 + 1, mid + 1, r,d);   //向右更新
    	mUp(p);  //更新叶节点
    }
    
    int main() {
    	scanf("%d %d %d", &N, &M, &R);
    	int tempN;
    	while (R--) {
    		scanf("%d", &tempN);
    		flag = false;
    		curLayer = 0;
    
    		segModified(1, 1, N, tempN);
    
    		if (flag) {
    			printf("%d\n", curLayer);
    		}
    		else {
    			printf("-1\n");
    		}
    	}
    
    	system("PAUSE");
    	return 0;
    }