HDU 2795 (线段树 单点更新) Billboard

h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子。

每次找能放纸条而且是最上面的位置,询问完以后可以同时更新,所以可以把update和query写在同一个函数里。

 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ; int _max[maxn << ];
int h, w, n, qL, qR, v; void build(int o, int L, int R)
{
if(L == R) { _max[o] = w; return; }
int M = (L + R) / ;
build(o*, L, M);
build(o*+, M+, R);
_max[o] = max(_max[o*], _max[o*+]);
} int query(int o, int L, int R)
{
if(L == R) { _max[o] -= v; return L; }
int M = (L + R) / ;
int ans;
if(_max[o*] >= v) ans = query(o*, L, M);
else ans = query(o*+, M+, R);
_max[o] = max(_max[o*], _max[o*+]);
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); while(scanf("%d%d%d", &h, &w, &n) == )
{
if(h > n) h = n;
build(, , h);
for(int i = ; i < n; i++)
{
scanf("%d", &v);
if(_max[] < v) puts("-1");
else printf("%d\n", query(, , h));
}
} return ;
}

代码君

上一篇:C#7的新语法


下一篇:Visual Studio 2019 远程调试工具(Remote Debugger)使用方法