题意：在一个h*w的矩阵中， 放置n个1* wi的矩阵，矩阵是水平放入，尽量往原矩阵的左上放(下面不能为空，像叠砖头一样)。 求每一次放入的高度。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <map> #include <set> #include <queue> #include <vector> #define mem(a) memset(a, 0, sizeof(a)) using namespace std; typedef pair<int, int> Pii; typedef long long LL; const int MAXN = 800005;//20w的四倍 const int inf = 0x3f3f3f3f; const int Mod = 100000000; struct node { int l, r; LL w; } tree[MAXN]; LL ans; void build(LL k, LL l, LL r, LL w) { tree[k].l=l; tree[k].r=r; tree[k].w=w; int mid = (l+r)>>1; if(tree[k].l==tree[k].r) return; build(k<<1|1,mid+1, r, w); build(k<<1, l, mid, w); return ; } void Insert(LL k, LL num) { if(tree[k].l==tree[k].r) { tree[k].w-=num; ans=tree[k].l; return; } if(num<=tree[k<<1].w) Insert(k<<1, num); else Insert(k<<1|1, num); tree[k].w=max(tree[k<<1|1].w, tree[k<<1].w); return; } int main() { LL n, h, w; LL num; while(~scanf("%lld %lld %lld", &h, &w, &n)) { if(h>n) h=n; build(1,1,h,w); for(int i=1; i<=n; ++i) { scanf("%lld", &num); ans=-1; if(num<=tree[1].w) Insert(1, num); printf("%lld\n", ans); ans=-1; } } return 0; }