线段树(单点更新) HDOJ 2795 Billboard
2024-08-30 14:45:10
/*
主要利用线段树求区间最值,sum[]代表位置可用空间
每次找到最大值的位置
功能:查询最靠前能容纳广告的位置
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1 const int MAX_N = + ;
int w[MAX_N];
int num[MAX_N];
int sum[MAX_N << ];
int n, h, W; void maxsum(int rt)
{
sum[rt] = std::max (sum[rt << ], sum[rt << | ]);
} void build(int l, int r, int rt)
{
sum[rt] = W;
if (l == r) return ;
int m = (l + r) >> ;
build (lson);
build (rson);
} int query(int p, int l, int r, int rt)
{
if (l == r)
{
sum[rt] -= p; //如果可以用,更新sum,update在query里做了
return l; //返回该位置
}
int m = (l + r) >> ;
int ans;
if (p <= sum[rt << ]) //如果p小于左孩子的最大值,则往左边下去
ans = query (p, lson);
else
ans = query (p, rson);
maxsum (rt); return ans;
} int main(void) //HDOJ 2795 Billboard
{
//freopen ("inD.txt", "r", stdin); while (~scanf ("%d%d%d", &h, &W, &n))
{
if (h > n) // h <= n
h = n; build (, h, ); int x;
while (n--)
{
scanf ("%d", &x);
if (x > sum[]) printf ("%d\n", -); //所有位置的最大值
else printf ("%d\n", query(x, , h, ));
}
} return ;
}
最新文章
- WPS for Linux(ubuntu)字体配置(字体缺失解决办法)
- C语言解决八皇后问题
- 在Delphi中如何控制其它应用程序窗口
- 必须会的SQL语句(五)NULL数据处理和类型转换
- win7中的Uac与开机自动启动(好几种办法,特别是用不带UAC的程序启动UAC程序是一个简单的好办法,写驱动自启动更是了不得)
- ASP.NET 5 :读写数据库连接字符串
- hosts.deny 和hosts.allow 配置不生效
- 算法模板——sap网络最大流 3(递归+邻接表)
- code force 403C.C. Andryusha and Colored Balloons
- Flex中配置FusionCharts
- 范型方法 &; 范型参数 &; 范型返回值
- [LeetCode] 620. Not Boring Movies_Easy tag: SQL
- MVC 之 初识(一)
- 20170907wdVBA_GetCellsContentToExcel
- Python中的转换函数
- 【LOJ】#2078. 「JSOI2016」无界单词
- poj1050最大子矩阵和
- 理解Defer、Panic和Recover
- python2.7下同步华为云照片的爬虫程序实现
- 关于Web项目出现懒加载异常的解决方案
热门文章
- ASP.NET MVC判断基于Cookie的Session过期
- DRF 之 版本控制
- ABAP range 用法
- C++11 条件变量
- opencv IplImage各参数详细介绍以及如何从一个JPEG图像数据指针转换得到IplImage
- Oracle:ORA-01790: expression must have same datatype as corresponding expression
- STL Algorithms 之 unique
- lucene Index Store TermVector 说明
- CollectionView网格布局
- 1 model的创建