二分：
使用二分必须保证数列是有序递增数列，下边是实现代码
int up_down( int *num, int l, int r, int key )
{
int mid;
while ( l < r ) {
//有些人也会写l<=r，但有个小胖子要我这么写
mid = l+(r-l)/2; //相当于（ｌ＋ｒ）/２，还是那个小胖子非要我这么写......
if ( num[mid] >= key )
r = mid;
else
l = mid+1; //这样l就是所救ｋｅｙ的最左边的下标
}
return l;
}
下面是一些例题
Turn It Off
Time Limit: 1 Second Memory Limit: 65536 KB
It’s already 21:30 now, and it’s time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off.
There are lights, numbered from 1 to , arranged in a row in BaoBao’s bedroom. Each time BaoBao can select an integer and turn all the lights numbered from to (both inclusive) off, where is a predefined positive integer. Note that each time the value of must be the same.
Given the initial status of all the lights, please help BaoBao determine the smallest possible so that he can turn all the lights off within times.
Input
There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
The first line contains two integers n and k ().
The second line contains a string (, ) indicating the initial status of the lights. Let be the -th character in , if then the -th light is initially on, otherwise it’s initially off. It’s guaranteed that there is at least one ‘1’ in .
It’s guaranteed that the sum of of all test cases will not exceed .
Output
For each test case output one line containing one integer, indicating the smallest possible .
Sample Input
2
10 4
0101011111
3 1
010
Sample Output
3
1
题目思路：用二分的方法，让ｌｅｆｔ＝１，ｒｉｇｈｔ＝总灯数，ｋｅｙ为每次熄灭的灯数，用ｎ来记录总次数，只要ｎ小于等于ｋ即可，最后输出最小的ｋｅｙ，也就是ｌｅｆｔ。
#include <stdio.h>
#include <string.h>
char a[200100];
int main()
{
int t, n, k, left, right, mid, i, l;
scanf("%d", &t);
while ( t-- ) {
scanf("%d %d", &n, &k);
scanf("%s", a);
right = n;
left = 1;
while ( left < right ) {
mid = (left+right)/2;
i = l = 0;
while ( i < n ) {
if ( a[i] == '0' ) {
//每次开始熄灭灯前，先跳过熄灭的灯。
i++;
continue;
}
i+=mid;
l++;
}
if ( l <= k ) {
right = mid;
}
else
left = mid+1;
}
printf("%d\n", left);
}
return 0;
}
POJ - 2785 4 Values whose Sum is 0
给你四个数列A,B,C,D。从每个数列中各取出一个数，使4个数的和为0.
当一个数列中有多个相同的数字的时候，把它们当做不同的数对待
Input第一行：n（代表数列中数字的个数） （1≤n≤4000）
第二行：依次输入A,B,C,D（输入一个A再输入一个B）
Output输出不同组合的个数。
Sample Input6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Sample Output5
HintSample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
题目思路：可以分别把ａｂ，ｃｄ两个数组的所有情况加起来，然后再统计两个数组中相加等于零的次数。注意：因为每个数组中的数有重复的，但这些情况还要计算其中。
#include <stdio.h>
#include <stdlib.h>
#define MAX 4100
int a[MAX], b[MAX], c[MAX], d[MAX],m[MAX*MAX], n[MAX*MAX];
int cmp ( const void *a , const void *b ) //这个ｃｍｐ是升序排列的
{
return *(int *)a - *(int *)b;
}
int up_down( int *num, int l, int r, int key )
{
int mid;
while ( l < r ) {
mid = (l+r)/2;
if ( num[mid] + key >= 0 )
r = mid;
else
l = mid+1;
}
if ( (num[l] + key) == 0 ) //如果前面的数组中的元素有和ｋｅｙ相加为０，则返回最左边这个数的下标，负责返回－１
return l;
else
return -1;
}
int main()
{
int N, i, j, k, e, f, ans;
scanf("%d", &N);
for ( i = 0; i < N; i++ ) {
scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
}
k = 0;
for ( i = 0; i < N; i++ ) {
//分别将ａｂ，ｃｄ中的值相加存到ｍ，ｎ数组中
for ( j = 0; j < N; j++ ) {
m[k] = a[i]+b[j];
n[k++] = c[i]+d[j];
}
}
qsort(m, k, sizeof(int), cmp); //头文件为<stdlib.h>
ans = 0;
for ( i = 0; i < k; i++ ) {
//遍历ｎ中的元素，在ｍ中用二分查找与ｎ中相加为０的数
e = up_down(m,0,k-1,n[i]);
if ( e != -1 ) {
ans++;
for ( f = e+1; f < k; f++ ) {
//从最左边的这个数的下标往后递增，当数字不同时停止，这样就可以找到这个数的总数
if ( m[e] == m[f] )
ans++;
else
break;
}
}
}
printf("%d\n", ans);
}