HDU 2795 Billboard （线段树：区间查询最大值）Billboard

72 阅读 0 评论 48 点赞

我是靠谱客的博主现实羊，最近开发中收集的这篇文章主要介绍HDU 2795 Billboard （线段树：区间查询最大值）Billboard，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Billboard

Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19799 Accepted Submission(s): 8277

Problem Description

At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.

On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.
Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi.
When someone puts a new announcement on the billboard, she would always choose the topmost possible position for the announcement. Among all possible topmost positions she would always choose the leftmost one.

If there is no valid location for a new announcement, it is not put on the billboard (that's why some programming contests have no participants from this university).
Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.

Input

There are multiple cases (no more than 40 cases).
The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions of the billboard and the number of announcements.

Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement.

Output

For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows are numbered from 1 to h, starting with the top row. If an announcement can't be put on the billboard, output "-1" for this announcement.

Sample Input

Sample Output

Author

hhanger@zju

Source

HDOJ 2009 Summer Exercise（5）

Recommend

lcy | We have carefully selected several similar problems for you: 1542 1828 1540 1255 2871

题意：给你一个h*w表格，和n个操作，每个操作给你一个1*Wi的格子。问你这个格子在哪一行。规定优先从上到下和从左到右。题目样例如下图：

题解：每次找到最大值的位置。然后再减去Wi。线段树查询区间最大值的位置。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")
//#include<bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
#include <iomanip>
#include <list>
#include <stack>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
const double eps = 1e-8;
const int INF = 1e9+7;
const ll inf =(1LL<<62) ;
const int MOD = 1e9 + 7;
const ll mod = (1LL<<32);
const int N =1e6+6;
const int M=100010;
const int maxn=200010;
#define mst(a) memset(a, 0, sizeof(a))
#define M_P(x,y) make_pair(x,y)
#define in freopen("in.txt","r",stdin)
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson
l , mid , rt << 1
#define rson
mid + 1 , r , rt << 1 | 1
const int lowbit(int x) { return x&-x; }
//const int lowbit(int x) { return ((x)&((x)^((x)-1))); }
int read(){ int v = 0, f = 1;char c =getchar();
while( c < 48 || 57 < c ){if(c=='-') f = -1;c = getchar();}
while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();
return v*f;}
int h,w,n;
int MAX[maxn<<2];
void pushup(int rt)//把当前结点的信息更新到父结点
{
//线段树是用数组来模拟树形结构
//对于每一个节点rt,左子节点为 2*rt (一般写作rt<<1)右子节点为 2*rt+1（一般写作rt<<1|1）
MAX[rt] = max( MAX[rt<<1] , MAX[rt<<1|1] );
}
void build(int l,int r,int rt)
{
MAX[rt] = w;
if(l==r) return ;
int mid=(l+r)>>1;
build(lson);//递归构造左子树
build(rson);//递归构造右子树
}
int query(int x, int l,int r,int rt) //区间减
{
if(l == r){
MAX[rt] -= x;
return l;
}
int mid = (l+r) >> 1;
int ans;
if( MAX[rt<<1] >= x) ans=query(x,lson);
else ans=query(x,rson);
pushup(rt);
return ans;
}
int main()
{
while(~scanf("%d%d%d",&h,&w,&n))
{
if(h > n) h = n;
build(1,h,1);
while(n--)
{
int x;
scanf("%d",&x);
if( MAX[1] < x ) cout<<-1<<endl;
else printf("%dn",query(x,1,h,1));
}
}
return 0;
}