题目传送门

 /*
主要利用线段树求区间最值,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 ;
}

最新文章

  1. WPS for Linux(ubuntu)字体配置(字体缺失解决办法)
  2. C语言解决八皇后问题
  3. 在Delphi中如何控制其它应用程序窗口
  4. 必须会的SQL语句(五)NULL数据处理和类型转换
  5. win7中的Uac与开机自动启动(好几种办法,特别是用不带UAC的程序启动UAC程序是一个简单的好办法,写驱动自启动更是了不得)
  6. ASP.NET 5 :读写数据库连接字符串
  7. hosts.deny 和hosts.allow 配置不生效
  8. 算法模板——sap网络最大流 3(递归+邻接表)
  9. code force 403C.C. Andryusha and Colored Balloons
  10. Flex中配置FusionCharts
  11. 范型方法 &amp; 范型参数 &amp; 范型返回值
  12. [LeetCode] 620. Not Boring Movies_Easy tag: SQL
  13. MVC 之 初识(一)
  14. 20170907wdVBA_GetCellsContentToExcel
  15. Python中的转换函数
  16. 【LOJ】#2078. 「JSOI2016」无界单词
  17. poj1050最大子矩阵和
  18. 理解Defer、Panic和Recover
  19. python2.7下同步华为云照片的爬虫程序实现
  20. 关于Web项目出现懒加载异常的解决方案

热门文章

  1. ASP.NET MVC判断基于Cookie的Session过期
  2. DRF 之 版本控制
  3. ABAP range 用法
  4. C++11 条件变量
  5. opencv IplImage各参数详细介绍以及如何从一个JPEG图像数据指针转换得到IplImage
  6. Oracle:ORA-01790: expression must have same datatype as corresponding expression
  7. STL Algorithms 之 unique
  8. lucene Index Store TermVector 说明
  9. CollectionView网格布局
  10. 1 model的创建