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;
}
}
}
~~~