Binary Search

题目链接 题意： # 在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n).

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

题意：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。

题目链接 题意：求一个BST中某两个节点LCA…. 思路：卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。

题目链接 d:题意：一棵树，给出边权和点权，定义点v控制点u，当且仅当u是v的子树中的点，并且dis(u,v)<=a[u]，其中dis(u,v)为点u到点v路径上的边权和，a[u]为点u的点权，现在问对于每个节点v，其能控制的点有多少个。

题目链接 题意：n只青蛙，第i只位于x[i],舌头长度为t[i]。m只蚊子，第i只蚊子所在位置为p[i],蚊子的大小为b[i]。

题意：给出n个数，两两做差的绝对值，共有m=n*(n-1)/2个，问其中的中位数是多少。特别地，当m为偶数的时候，中位数为第m/2个。

题目链接 题意：给出n个x轴上的坐标点，选取其中c个，问c个之中任意两个点的最小距离最大是多少。

题目链接 题意：把一个长度为n的只由数字构成的串分成k个不为空的字串，使得最大的串最小（大小是说串所对应的十进制数的大小）

cf689C 题意：给出一个m。。问恰好使得不超过某个n的a*b^3（a,b是正整数）的方案数为m的n是多少。。。

1614: [Usaco2007 Jan]Telephone Lines架设电话线 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1325 Solved: 570 [Submit][Status][Discuss]

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。

1650: [Usaco2006 Dec]River Hopscotch 跳石子 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 440 Solved: 290 [Submit][Status][Discuss]

1639: [Usaco2007 Mar]Monthly Expense 月度开支 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 767 Solved: 381 [Submit][Status][Discuss]

题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]],相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。

http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)