?
题目传送：Billboard
思路：有一个h*w的木板（可以看成h行，每行最多放w的空间），每次放1*L大小的物品，返回最上面可以容纳L长度的位置，没有则输出-1；
AC代码：
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define INF 0x7fffffff using namespace std; const int maxn = 200005; int h, w, n; int a[maxn << 2]; void build(int l, int r, int rt) { //建树，记录最大值 a[rt] = w; if(l == r) return; int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); } int query(int x, int l, int r, int rt) { //查询并更新 if(l == r) { //找到位置，更新并且返回当前位置 a[rt] -= x; return l; } int mid = (l + r) >> 1; int ret; if(a[rt << 1] >= x) ret = query(x, l, mid, rt << 1); else ret = query(x, mid + 1, r, rt << 1 | 1); a[rt] = max(a[rt << 1], a[rt << 1 | 1]); return ret; } int main() { while(scanf("%d %d %d", &h, &w, &n) != EOF) { if(h > n) h = n; //优化，当h比n大时用不到这么多，可以去掉多余的 build(1, h, 1); for(int i = 0; i < n; i ++) { int x; scanf("%d", &x); if(a[1] < x) puts("-1"); else printf("%d\n", query(x, 1, h, 1));//这里h写成n了，检查半天(⊙?⊙)b } } return 0; }