题目链接

题意：

在一个二维平面上，有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.

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

For example, in 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.

思路：找规律。。。二分。。。

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, …

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.

好像阿里一面的时候问过。。。

思路：肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。

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

题目链接

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

思路：单调。。显然二分。。。唯一的技巧是从右上角开始搜。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年03月09日 星期四 19时03分07秒
 4File Name :74.cpp
 5************************************************ */
 6class Solution {
 7
 8public:
 9
10    bool …

题目链接

题意：求一个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个之中任意两个点的最小距离最大是多少。

思路：二分距离check合法性。

大水题。。。因为想把三分艹掉。。。三分的题又多和二分挂在一起。。。顺便就写了。。。。

题目链接

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

思路：由于长度为x的串肯定大于长度为x-1的串，因此很容易想到，我们要尽可能使得k组串的长度尽可能平均（避免出现某一个串的长度非常大的情况）

cf689C

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

思路：暴力+二分。。。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年07月18日 星期一 15时58分55秒
 4File Name :code/2016whust/G.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include …

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)对电话线杆间可以拉电话 …

poj2452题目链接

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

思路：大概能想到是rmq，然后想出了一个错误复杂度的错误思路，还直到对拍才发现==

1650: [Usaco2006 Dec]River Hopscotch 跳石子

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 440  Solved: 290 [Submit][Status][Discuss]

Description

Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, …

1639: [Usaco2007 Mar]Monthly Expense 月度开支

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 767  Solved: 381 [Submit][Status][Discuss]

Description

Farmer John是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每个月的正常运转的。他已经计算了他以后N(1<=N<=100,000)个工作日中每一天的花费moneyi(1<=moneyi<=10,000)，他想要为他连续的M(1<=M<=N)个被叫做“清算月”的结帐时期做一 …

题目链接 题意：有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)