HDU2795（线段树+单点更新+思维）
题目大意：给一个h高，w宽的广告牌，以及n条广告的宽度，每条广告的高度默认为1，问n条广告能插上的话所在的最高行数，插入不了输入-1.
解题思路：比较容易到用mlen维护区间h能够装下的最长广告的长度（未插入），n在2e5内，所以线段树最多就开8e5就足够了！之后单点更新的时候顺带返回下标。
Code:
#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)2e5+5;
struct Node {
int l, r;
int mlen;
};
Node BTree[maxn << 2];
int val[maxn];
int w,h,n;
inline void PushUp(int idx) {
BTree[idx].mlen = max(BTree[idx << 1].mlen, BTree[idx << 1 | 1].mlen);
}
void bulid(int l, int r, int idx) {
BTree[idx].l = l;
BTree[idx].r = r;
if (l == r) {
BTree[idx].mlen = w;
return ;
}
int mid = l + (r - l >> 1);
bulid(l, mid, idx << 1);
bulid(mid + 1, r, idx << 1 | 1);
PushUp(idx);
}
//单点更新 返回更新的位置
int update(int num, int idx) {
if (BTree[idx].l == BTree[idx].r) {
if (BTree[idx].mlen >= num)
BTree[idx].mlen -= num;
else
return -1; //特判点
return BTree[idx].l;
}
int flag = -1;
if (BTree[idx << 1].mlen >= num) {
flag = update(num, idx << 1);
} else if (BTree[idx << 1 | 1].mlen >= num) {
flag = update(num, idx << 1 | 1);
}
PushUp(idx);
return flag;
}
int main() {
while (scanf("%d%d%d", &h, &w, &n) != EOF) {
if (h > n) h = n;
for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
bulid(1, h, 1);
for (int i = 1; i <= n; i++) {
printf("%d\n", update(val[i], 1));
}
}
return 0;
}
查看29道真题和解析