集训队作业poi188道解题报告poi18pio

1、POI18pio解题报告杭州学军中学 高欣题目简述有n幢建筑在一条直线上，编号从1到n，每幢建筑有一个高度hi。在i号建筑上安装长度为p的避雷针，能保护到j的条件是对于每个i，在i上安装避雷针使得它能保护所有建筑，最短的避雷针长度是多少。n 500000算法分析在求pi的时候，p如果只考虑i左边的j，式子就变成了p考虑两个决策j和k（jhj+i-j的最小的于是我们维护一个决策的队列满足相邻两个决策的f值是单调递增的。队列头部元素就是使得hj+i-j最大的j。随着如果头部元素比下一个更劣，删去头部元素。删去尾部一段元素，使得加入i这个决策后f值仍然单调。队列里面总共的删除添加操作是O(n)的，关

2、键是怎么求f(j,k)。一种很方便的方法就是二分法，时间复杂度是O(nlogn)，预处理开平方根的运算就可以AC。仔细观察，其实hk+i-k=hj+i-j可以转化为一次方程，直接解出来就可以了，求f(j,k)只要O(1)的时间。原题Lightning ConductorMemory limit: 128 MBProgressive climate change has forced the Byteburg authorities to build a huge lightning conductor that would protect all the buildings within th

3、e city. These buildings form a row along a single street, and are numbered fromto.The heights of the buildings and the lightning conductor are non-negative integers. Byteburgs limited funds allow construction of only a single lightning conductor. Moreover, as you would expect, the higher it will be,

4、 the more expensive.The lightning conductor of heightlocated on the roof of the building(of height) protects the building(of height) if the following inequality holds:wheredenotes the absolute value of the difference betweenand.Byteasar, the mayor of Byteburg, asks your help. Write a program that, f

5、or every building, determines the minimum height of a lightning conductor that would protect all the buildings if it were put on top of the building.InputIn the first line of the standard input there is a single integer() that denotes the number of buildings in Byteburg. Each of the followinglines holds a single integer() that denotes the height of the-th building.OutputYour program should print out exactlylines to the standard output. The-th line should give a non-negative integerdenoting the minimum height of the lightning conductor on the-th building