本文共 3309 字，大约阅读时间需要 11 分钟。

只知道数据结构的一点皮毛，突然听说有个PAT考试，不管有用没用先报名了，还有一个整月，抱一本《算法笔记》压压惊，祝福我自己>_<。

• 问题：寻找有序序列中第一个满足某条件的元素的位置。这个条件是从序列左起到右，从不满足条件到开始满足。

例如：

if(A[mid] >= x)

2). 从小到大排序的数列中，从左到右找到第一个大于x的位置，条件可以设置为

if(A[mid]>x)

3). 从大到小排序的数列中，找到最小的一个大于等于x的位置，即从右到左找到第一个大于等于x的位置。相当于从左到右寻找第一个小于x的位置并且-1。条件可以设置为

if(A[mid] < x)//最终返回值为return left -1;

模板为：

int solve(int left,int right){	int mid;	mid = (left + right)/2;	while(left < right){		if(条件成立){			right = mid;		}else{			left = mid + 1;		}		return left;}

等价于

int solve(int left,int right){	int mid;	mid = (left + right)/2;	while(left +1< right){		if(条件成立){			right = mid;		}else{			left = mid;		}		return right;}

• 问题：查找序列中是否存在满足某条件的元素，用最常用的写法即可

int find(int A[],int left,int right,int x){	int mid;	while(left <= right){		mid = (left + right)/2;		if(A[mid] == x) return mid;		else if (A[mid]  >x){			right = mid-1;		}		else{			left = mid+1;		}	}	return -1;}

两个具体的题目

1. 木棒切割问题：给出N根木棒，长度均已知，现在希望通过切割它们得到至少K段长度相等的木棒（长度必须是整数），问这些长度相等的木棒最长能有多长。例如三根长度分别为10、24、15的木棒来说，K=7，那么最大长度为 6。
   分析：长度越长，得到的总段数越少；若把长度作为数组的下表，那么数组就是一个由大到小排序。想要找下标最大，即值最小的但$k\ge K$的值。把条件变成第一个满足条件$k<K$的位置。

#include 
   
    int sumk(int A[],int n,int l){	int re=0;	for(int i=0;i
   

2. 给出N个线段长度，试将它们头尾相接（顺序任意），组合成一个凸多边形，使得该凸多边形的外接圆（即能使凸多边形的所有顶点都在圆周上的圆）的半径最大，求最大半径。其中N不超过$10^5$，线段长度不超过100，要求算法中不涉及坐标的计算。
   分析：

• 首先半径一定大于等于最长线段的一半。
• 这题的意思是这些线段组成的凸多边形的顶点一定能放在某个圆上，我们只需要考虑半径最大就行，不用考虑如何组成的这种图形。
• 如果圆心在凸多边形的内部，假设最大半径是$\hat{r}$，这时所有的线段对应的圆心角之和为$2\ast \pi$。
  • 如果半径比$\hat{r}$大，那么这些线段的圆心角之和$sum<2\ast \pi$，线段没法首尾相连的在外接圆上，半径应变小。
  • 如果半径比$\hat{r}$小，那么这些线段的圆心角之和$sum>2\ast \pi$，这时构成的外接圆不是半径最大的外接圆，半径应变大。
  • 因此可以对半径长度二分，寻找圆心角之和为$2\ast \pi$的那个值即可。
• 如果圆心在凸多边形的外部，假设最大半径是$\hat{r}$，那么最长的线段的圆心角，一定等于其他线段的圆心角之和。取计算目标为 $其他圆心角和+2\pi -最大圆心角$，此时情况取反。
  • 举例，半径4，有圆心角90度的线段长$8\ast sin(\frac{\pi }{4})=5.65$，两个圆心角45度的线段长$8\ast sin(\frac{\pi }{8})=3.06$。
  • 如果半径变为3，原5.65线段圆心角变为141度；原3.06线段圆心角变为62度；这时$其他圆心角-最大圆心角+2\pi <2\pi$，此时半径应变大。

const double PI = acos(-1.0);const double eps = 1e-5;//求圆心角之和double totalCornerAngles(double edges[], int n, double r) {	double sum = 0.0;	for (int i = 0; i < n; i++) {		sum += asin(edges[i] / r / 2) * 2;	}	return sum;}//2分求半径double radius(double A[],int n) {	double left,right, mid;	//最大线段的圆心角，剩余线段的圆心角和	double maxangle, other;	//最大线段长	double maxedge = *max_element(A, A + n);	//如果最大线段恰好是直径	double sum = totalCornerAngles(A, n, maxedge / 2);	if (fabs(sum - PI) < eps) {		return max_ridge / 2;	}	//半径应大于最大线段的一半	left = maxedge / 2, right = 100;	//循环求解	while ((right - left) > eps) {		mid = (left + right) / 2;		maxangle = asin(maxedge / 2 / mid) * 2;		sum = totalCornerAngles(A, n, mid);		other = sum - maxangle;		//如果其他圆心角之和小于pi,圆心在多边形外面		if (other < PI) {			sum = other - maxangle + 2 * PI;			if (fabs(sum - 2 * PI) < eps) {				return mid;			}			else if (sum < 2 * PI) {				left = mid;			}			else {				right = mid;			}		}		else {   //否则在内部			if (fabs(sum - 2 * PI) < eps) {				return mid;			}			else if (sum > 2 * PI) {				left = mid;			}			else {				right = mid;			}		}			}}

转载地址：http://xeldz.baihongyu.com/