1.二分查找

解决寻找有序序列中第一个满足某条件的元素的位置的固定模板 1.A[ ]为递增序列，x为欲查询的数，函数返回第一个大于等于x的元素的位置 二分的上下界为左闭右闭的[left,right]，传入的初值为[0,n]

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

注：如果返回第一个大于x的元素，只需要把 if(A[mid]>=x)修改为 if(A[mid]>x)

2. A1044 Shopping in Mars

Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:

Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15). Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15). Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).

Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer. If it is impossible to pay the exact amount, you must suggest solutions with minimum lost. Input Specification: Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤10​5​​), the total number of diamonds on the chain, and M (≤10​8​​), the amount that the customer has to pay. Then the next line contains N positive numbers D​1​​⋯D​N​​ (D​i​​≤10​3​​ for all i=1,⋯,N) which are the values of the diamonds. All the numbers in a line are separated by a space. Output Specification: For each test case, print i-j in a line for each pair of i ≤ j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i. If there is no solution, output i-j for pairs of i ≤ j such that Di + … + Dj >M with (Di + … + Dj −M) minimized. Again all the solutions must be printed in increasing order of i. It is guaranteed that the total value of diamonds is sufficient to pay the given amount.

Sample Input 1:

16 15 3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13

Sample Output 1:

1-5 4-6 7-8 11-11

Sample Input 2:

5 13 2 4 5 7 9

Sample Output 2:

2-4 4-5

算法思路：

1.令sum[i]=a[1]+a[2]+…+a[i],sum[i]是严格单调递增的，sum[i]-sum[j]就表示 j+1 到 i 的序列和，由于数字都是正数，所以sum[i]一定是递增的。例如a={1,2,3,4,5}，sum={1,3,6,10,15},要计算a[3]~a[5]，则只要计算sum[5]-sum[2]=12. 2.对sum数组进行二分，枚举左端点i，sum[j]-sum[i-1]=S作为条件，用上述函数查找第一个大于sum[i-1]+S的点的位置，返回 j。如果sum[j-1]-sum[i-1]=S，则找到一个序列，进行标记nearS=S，如果没有则标记sum[j]-sum[i-1]=nearS的值，这个值一定是第一轮枚举过程里，最接近于S的数，在此后的枚举中，如果没有出现等于S的序列，则不停的去比较更新nearS的最小值。 3.最后只需要重新遍历，找到序列和等于nearS的序列，输出即可。

算法笔记书代码伪码：

int upper_bound();//上面写的返回第一个大于某数的位置 int main（）{ sum[0]=0; //i=1开始输入并计算出sum数组 //枚举左边端点 for(int i=1;i<=n;i++){ int j=upper_bound();//右端点 if(sum[j-1]-sum[i-1]==S){//查找成功 nearS=S; break; }else if{j<=n&&sum[j]-sum[i-1]<nearS){ nearS=sum[j]-sum[i-1]; //失败，找最接近S的点 } } for(){ int j=upper_bound(); if(sum[j-1]-sum[i-1]==nearS){ //输出 } } } }

原题：

PAT1044