题意是有一张n*m的广告牌,然后有t张1*xi的广告,每张广告都尽量往上往左贴,然后输出第xi张广告所在的行数,如果贴不下的话就输出-1。
思路就是初始化每个结点为m值,表示可以贴长度为m的广告,然后Pushup函数维护一个区间的最大值,然后贴广告的时候优先贴左节点就好了。不懂的可以问。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
#define maxn 200005
using namespace std;
int sum[maxn << 2],pre[maxn];
int n,m,T;
string str;
void Pushup(int o){
sum[o] = max(sum[o << 1] , sum[o << 1 | 1]);
}
void Build(int l, int r, int o){
if(l == r){
sum[o] = m;
return ;
}
int mid = (l + r) >> 1;
Build(lson);
Build(rson);
sum[o] = m;
}
void Query(int x, int l, int r, int o){
if(x > sum[o]){
printf("-1\n");
return ;
}
if(l == r){
sum[o] -= x;
printf("%d\n",r);
return ;
}
int mid = (l + r) >> 1;
int ans = 0;
if(x <= sum[o << 1]) Query(x, lson);
else{
Query(x, rson);
}
Pushup(o);
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&T)){
int t = min(T,n);
Build(1,t,1);
for(int i=0;i<T;i++){
int x;
scanf("%d",&x);
Query(x,1,t,1);
}
}
return 0;
}