hdoj 2795 Billboard

2015-12-17 · 1 min read · 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个，放在最上面（编号小）思路：把没横行能放的最大长度看做一个序列建树。由于h比n大很多。。多出来的没用。。直接取较小值就行。

/* ***********************************************
Author :111qqz
Created Time :2015年12月17日 星期四 15时04分52秒
File Name :code/hdu/2785.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E5+7;
7int h,w,n;

1struct SegTree   //将每个横格能放置的最大长度看做一个序列，建树。
2{
3    int mx; 
4}tree[4*N];

 1void build ( int l,int r,int rt)
 2{
 3  //  cout<<"l:"<<l<<" r:"<<r<<" rt:"<<rt<<endl;
 4    tree[rt].mx = w;
 5    if (l==r)
 6    {
 7	return ;
 8    }
 9    int m = (l+r)>>1;
10    build (lson);
11    build (rson);

 1int query( int x,int l,int r,int rt)
 2{
 3    if (l==r)
 4    {
 5	tree[rt].mx-=x;  //将长度为x的改点放在第l个横格里。
 6	return l;
 7    }
 8    int m = (l+r)>>1;
 9    int res;
10    if (tree[rt<<1].mx>=x)  //先搜左子树，可以保证topmost.
11    {
12	res=query(x,lson);
13    }
14    else
15    {
16	res=query(x,rson);
17    }

1    tree[rt].mx = max(tree[rt<<1].mx,tree[rt<<1|1].mx);
2    return res;
3}

1int main()
2{
3	#ifndef  ONLINE_JUDGE 
4	freopen("code/in.txt","r",stdin);
5  #endif

 1	while (~scanf("%d %d %d",&h,&w,&n))
 2	{
 3	    if (h>n) h = n ;  //不用离散化，这样就可以。
 4	    build(1,h,1);
 5	    while (n--)
 6	    {
 7		int x;
 8		scanf("%d",&x);
 9		if (x>tree[1].mx)
10		{
11		    puts("-1");
12		}
13		else
14		{
15		    printf("%d\n",query(x,1,h,1));
16		}
17	    }
18	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}