Billboard

title: 题目
 
在学校的入口处有一个巨大的矩形广告牌,高为h,宽为w。所有种类的广告都可以贴,比如ACM的广告啊,还有餐厅新出了哪些好吃的,等等。。
 
在9月1号这天,广告牌是空的,之后广告会被一条一条的依次贴上去。
 
每张广告都是高度为1宽度为wi的细长的矩形纸条。
 
贴广告的人总是会优先选择最上面的位置来帖,而且在所有最上面的可能位置中,他会选择最左面的位置,而且不能把已经贴好的广告盖住。
 
如果没有合适的位置了,那么这张广告就不会被贴了。
 
现在已知广告牌的尺寸和每张广告的尺寸,求每张广告被贴在的行编号。
 
多组样例,不超过40个。
 
对每组样例,第一行包含3个整数h,w,n(1 <= h,w <= 10^9; 1 <= n <= 200,000) -广告牌的尺寸和广告的个数。  
  
下面n行每行一个整数 wi (1 <= wi <= 10^9) -  第i张广告的宽度
 
对每张广告,输出它被贴在的行编号(是1到h之间的数),顶部是第一行。如果某广告不能被贴上,则输出-1。
 
title: input
3 5 5
2
4
3
3
3
title: output
1
2
1
3
-1
title: 思路
给你的广告高度都是1, 故可以将广告牌的高度看做数组下标, 宽度为数组值, 一个广告放到数组1位置上时,就将其值减去广告宽度, 直到没法再加。
 
不能使用数组来模拟这个过程, 每次加时得从头往后找。
 
使用线段树, 记录区间的最大值, 这样如果这个区间的最大值都小于广告宽度, 就不再查找, 往另一个区间查找, 直到找到一个点。
 
找不到则输出-1即可
 
title:代码
~~~ c ++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10, M = 4 * N;
typedef long long ll;
int tree[M];
int h, w, n;
 
int readInt()
{
    int t;
    scanf("%d", &t);
    return t;
}
 
void ps(int node)
{
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]);
}
 
void build(int node, int L, int R)
{
    if (L == R)
    {
        tree[node] = w;
        return;
    }
    int mid = L + R >> 1;
    build(node << 1, L, mid), build(node << 1 | 1, mid + 1, R);
    ps(node);
}
 
int query(int node, int L, int R, int value)
{
    if (L == R)
    {
        tree[node] -= value;
        return L;
    }
    int mid = L + R >> 1;
    int res = 0;
    if (tree[node << 1] >= value)
        res = query(node << 1, L, mid, value);
    else if (tree[node << 1 | 1] >= value)
        res = query(node << 1 | 1, mid + 1, R, value);
    ps(node);
    return res;
}
 
int main()
{
    while (scanf("%d %d %d", &h, &w, &n) == 3)
    {
        h = min(h, n);
        build(1, 1, h);
        while (n--)
        {
            int t = readInt();
            if (t > tree[1])
                printf("-1\n");
            else
                printf("%d\n", query(1, 1, h, t));
            for (int i = 1; i <= h + 2; i++)
                cout << tree[i] << " ";
            cout << endl;
        }
    }
}
~~~