# 思路：

## leetcode162. Find Peak Element (O(lgn)复杂度寻找峰值)

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.

You may imagine that num[-1] = num[n] = -.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:Your solution should be in logarithmic complexity.

## leetcode 33. Search in Rotated Sorted Array (无重复数的旋转数组找定值)

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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

a[mid]>a[r]的时候，前半段有序。。

## leetcode 34. Search for a Range (二分，找到一段值为tar的区间)

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).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

## leetcode 81. Search in Rotated Sorted Array II (有重复元素的旋转数组找给定值)

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).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

## codeforces 381 div 2 D. Alyona and a tree(二分+前缀和)

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

upd:和lca没有什么关系，因为一个点能控制另一个点这两个点一定在一条通向根的链上，因此距离直接减一下就好了。

## poj 3579 Median (尺取法+二分)

check的条件是，以k为中位数的时候，绝对值小于k的数要小于(m+1)/2个（也就是中位数所在的位置）

check的时候尺取即可。

cf689C

## 1614: [Usaco2007 Jan]Telephone Lines架设电话线

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1325  Solved: 570
[Submit][Status][Discuss]

## Description

Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。 经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K对，那么FJ的总支出为0。 请你计算一下，FJ最少需要在电话线上花多少钱。

## Input

* 第1行: 3个用空格隔开的整数：N，P，以及K

* 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i

## Output

* 第1行: 输出1个整数，为FJ在这项工程上的最小支出。如果任务不可能完成， 输出-1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

## Sample Output

4

FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的