前言

5aSn5a626YO96KeJ5b6X5oiR5LqM5YiG6K6y5b6X5LiN5aW977yM5
omA5Lul5omT566X5YaZ5Liq5Y2a5a6i5p2l5byl6KGl44CC44CC44C

Tips:base64解码

0.二分入门

二分思想就是把一个大问题分解成许多个解法相同的小问题来解决，这样就可以把一个O(n)复杂度的程序优化成O(log n)的复杂度。

1.二分经典例题之循环赛日程表

【题目描述】
设有n=$2^k$个选手参加比赛，要求设计一个满足一下要求的比赛日程表:
（1）每个选手必须与其他的n-1个选手个比赛一次；
（2）每个选手每天只能赛一次 。
【输入格式】
只有一个正整数k
【输出格式】
请输出一个n行，每行有n个正整数的循环赛日程表。相邻的两个正整数用一个空格隔开。
其中，第i行（0<i<n+1）表示第i队的参赛日程，第1个正整数为i，表示参赛队的队号，后面的(n-1)个正整数表示该队在参赛日程中，依次较量的队号。
【样例输入】

1

【样例输出】

1 2
2 1

【说明】
0<k<9（k属于正整数）
【题解】
假设n位选手被顺序编号为1,2,3,…,n，比赛的日程表是一个n行n-1列的表格，i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则，可从其中一半选手($2^(n-1)$位)的比赛日程，导出全体n位选手的日程，最终细分到只有两位选手的比赛日程出发。
可假设只有8位选手参赛，若1至4号选手之间的比赛日程填在日程表的左上角(4行3列)，5至8号选手之间的比赛日程填在日程表的左下角(4行3列)；那么左下角的内容可由左上角的对应项加上数字4得到。至此，剩余的右上角(4行4列)是为编号小的1至4号选手与编号大的5至8号选手之间的比赛日程安排。例如，在第4天，让1至4号选手分别与5至8号选手比赛，以后各天，依次由前一天的日程安排，让5至8号选手“循环轮转”即可。最后，比赛日程表的右下角的比赛日程表可由，右上角的对应项减去数字4得到。

k=3时的图例：

选手 1天 2天 3天 4天 5天 6天 7天
1号 2 3 4 5 6 7 8
2号 1 4 3 6 7 8 7
3号 4 1 2 7 8 5 6
4号 3 2 1 8 5 6 5
左上角 右上角
5号 6 7 8 1 4 3 2
6号 5 8 7 2 1 4 3
7号 8 5 6 3 2 1 4
8号 7 6 5 4 3 2 1
左下角 右下角

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<cmath>
using namespace std;
int k;
int a[100][100];
int n,temp;
void gametable(int x)
{       
	n=2;//k=0两个参赛选手日程可以直接求得
	a[1][1]=1;a[1][2]=2;
	a[2][1]=2;a[2][2]=1;
	for(int t=1;t<x;t++)//迭代处理，依次处理2^n....2^k个选手的比赛日程
	{
		temp=n;n=n*2;//填左下角元素
		for(int i=temp+1;i<=n;i++)
			for(int j=1;j<=temp;j++)
				a[i][j]=a[i-temp][j]+temp;//左下角和左上角元素的对应关系
		for(int i=1;i<=temp;i++)//将左下角元素抄到右上角
			for(int j=temp+1;j<=n;j++)
				a[i][j]=a[i+temp][(j+temp)%n];
		for(int i=temp+1;i<=n;i++)//将左上角元素抄到右下角
			for(int j=temp+1;j<=n;j++)
				a[i][j]=a[i-temp][j-temp];
	}
	//第i行第j列表示和第i个选手在第j天比赛的选手序号
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}    
}
int main()
{
	scanf("%d",&k);
	if(k!=0)
		gametable(k);
	return 0;
}
//该程序取自网络，并非本人亲自所写

2.二分联赛例题之跳石头（noip2015）

【题目链接】
洛谷【P2678】跳石头
【题目背景】
一年一度的“跳石头”比赛又要开始了!
【题目描述】
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终 点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达 终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳 跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能 移走起点和终点的岩石)。
【输入格式】
输入文件名为 stone.in。
输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终 点之间的岩石数,以及组委会至多移走的岩石数。
接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与 起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同 一个位置。
【输出格式】
输出文件名为 stone.out。 输出文件只包含一个整数,即最短跳跃距离的最大值。
【输入样例】

25 5 2
2
11
14
17
21

【输出样例】

4

【说明】
输入输出样例 1 说明：将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

另：对于 20%的数据,0 ≤ M ≤ N ≤ 10。 对于50%的数据,0 ≤ M ≤ N ≤ 100。
对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。

【题解】
二分答案+贪心
所谓二分答案就是确定一个答案的范围，然后将这个范围进行二分，然后对mid进行判断，如果答案小于mid则二分mid的左半部分，反之二分mid的右半部分，最后左右端点重合（或者相差1），得到的就是答案。
这道题二分答案的判断部分用到的就是贪心，关于贪心的问题可以参考其他博客。
【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 50500
using namespace std;
int L,m,n,l,r,mid,ans,st;
int a[N];
int main()
{
	freopen("stone.in","r",stdin);
	freopen("stone.out","w",stdout); 
	scanf("%d%d%d",&L,&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	a[++n]=L;
	l=0;r=L;                 //将首尾的石头放入数组
	while(l<=r)              //这里用的是非递归的二分 
	{
		mid=(l+r)/2;
		//////check
		ans=0;st=0;
		for(int i=1;i<=n;++i)
		{
			if(a[i]-st<mid)
				ans++;             //符合条件，移走石头
			else
				st=a[i];           //不符合，从当前石头往后搜
		}
		if(ans>m)              //非递归二分格式
			r=mid-1;             
		else
			l=mid+1;
	}
	printf("%d",l-1);
	return 0;
}

3.二分奇怪例题之Franky的胡子（来自Franky大神的题目）

【题目链接】
COGS【2482】
【题目描述】
Franky很苦恼他一直不长胡子。
看到同学大叔一样的胡子，Franky总是很无耻的偷笑…
有一天，杨老师要带Franky参加n天的外出培训！！！好开心！！
在火车上，Franky突然发现自己长了胡子！
杨老师带Franky去查了基因图谱==（好贴心）
并且发现：
1.胡子初始每天深夜都会长v cm；
2.每次在剃掉胡子之后胡子增长的速度会增加s cm/天；
Franky很伤心，并且由于来时并不需要剃须刀，所以只能借杨老师的，但是杨老师很吝啬（哼( ﹁ ﹁ ) ~→）
他只允许Franky使用x次剃须刀，而且只允许在晚上睡前用。
【输入格式】
输入格式：
一行，n,s,v,x四个整数。
【输出格式】
输出在培训期间Franky的胡子最长的那天胡子的长度最短值。
【输入样例】

6 1 1 2

【输出样例】

4

【说明】
保证对于20%的数据,x,n,v,s<=10;
对于70%的数据,x,n<=5000,v,s<=100;
对于100%的数据,x,n<=100000,v,s<=10000.
【题解】
二分答案，二分胡子的长度，check剃胡子。
【程序】

long long卡了我半天。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<iostream>
#include<climits>
#define M 500500
using namespace std;
int n,v,s,x;
int check(long long k)
{
	long long vi=v,beard=0,xi=x;
	for(int i=1;i<=n;++i)
	{
		beard+=vi;
		if(beard>k)
		{
			vi+=s;
			beard=0;
			xi--;
			i--;
		}
		if(xi<0)
			return 0;
	}
	return 1;
}
int main()
{
	freopen("beard.in","r",stdin);
	freopen("beard.out","w",stdout);
	scanf("%d%d%d%d",&n,&s,&v,&x);
	long long l=0,r=77777777777777;
	long long mid;
	while(r-l>1)
	{
		mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<l+1;
	return 0;
}

注：Franky真是神犇！！！%%%Franky%%%

4.二分联赛例题之聪明的质监员（noip2011）

【题目链接】
洛谷【1314】
【题目描述】
小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1到n 逐一编号，每个矿石都有自己的重量 wi 以及价值vi 。检验矿产的流程是：
1 、给定m 个区间[Li ，Ri]；
2 、选出一个参数 W；
3 、对于一个区间[Li ，Ri],计算矿石在这个区间上的检验值Yi:
$Y_{i}=\sum_{j} 1*\sum_{j} v_{j}$,$j\in[L_{i},R_{i}]$且$w_{j}\ge W$,$j$是矿石编号。
这批矿产的检验结果Y为各个区间的检验值之和。即$Y=Y_{1}+Y_{2}+…+Y_{m}$。
若这批矿产的检验结果与所给标准值S 相差太多，就需要再去检验另一批矿产。
小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值S，
即使得S-Y 的绝对值最小。请你帮忙求出这个最小值。
【输入格式】
第一行包含三个整数n，m，S，分别表示矿石的个数、区间的个数和标准值。
接下来的n 行，每行2个整数，中间用空格隔开，第i+1 行表示 i 号矿石的重量 wi 和价值vi。
接下来的m 行，表示区间，每行2 个整数，中间用空格隔开，第i+n+1 行表示区间[Li,Ri]的两个端点Li 和Ri。注意：不同区间可能重合或相互重叠。
【输出格式】
输出只有一行，包含一个整数，表示所求的最小值。
【输入样例】

5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3

【输出样例】

10

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<iostream>
#define M 500500
#define LL long long
using namespace std;
LL n,m,s;
LL w[M],v[M];
LL li[M],ri[M];
LL a[M],b[M];
long long check(long long x)
{
	for(int i=1;i<=n;++i)
	{
		a[i]=0;
		b[i]=0;
	}
	for(int i=1;i<=n;++i)
	{
		if(w[i]>=x)
		{
			a[i]++;
			b[i]=v[i];
		}
		a[i]+=a[i-1];
		b[i]+=b[i-1];
	}
	LL ans=0,l,r;
	for (int i = 1;i <= m;i++)
	{
        l=li[i],r=ri[i];
        ans+=(a[r]-a[l-1])*(b[r]-b[l-1]);
    }
	return ans;
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=n;++i) scanf("%lld%lld",w+i,v+i);
	for(int i=1;i<=m;++i) scanf("%lld%lld",li+i,ri+i);
	LL l=0,r=7777777777777,mid;
	while(r-l>1)
	{
		mid=(l+r)>>1;
		if(check(mid)<=s) r=mid;
		else l=mid;
	}
	LL ans;
	ans=min(check(l)-s,-(check(l+1)-s));
	cout<<ans;
	return 0;
}

5.二分经典例题之归并排序求逆序对

归并排序

归并排序_百度百科

UP主很良(wu)心(liang)地粘了个百科的链接。。。

归并排序求逆序对

【题目链接】
POJ【1804】
【题目背景】
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.
【题目描述】
Here’s what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:
Start with: 2 8 0 3
swap (2 8) 8 2 0 3
swap (2 0) 8 0 2 3
swap (2 3) 8 0 3 2
swap (8 0) 0 8 3 2
swap (8 3) 0 3 8 2
swap (8 2) 0 3 2 8
swap (3 2) 0 2 3 8
swap (3 8) 0 2 8 3
swap (8 3) 0 2 3 8

So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:
Start with: 2 8 0 3
swap (8 0) 2 0 8 3
swap (2 0) 0 2 8 3
swap (8 3) 0 2 3 8

The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond’s mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.
【大概翻译】
给定一个序列,每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列.
【输入格式】
第一行输入情景数n.
接下来n行，每一行第一个数表示序列长度为N（1≤N≤1000），其次是N个元素的序列（每个元素是一个整数，在[-1000000，1000000]）。在这一行的数字都是由单个空格分隔。
【输出格式】
对于每个情景，先输出”Scenario #i:”（i从1开始递增），然后输出最小的交换次数。
【输入样例】

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

【输出样例】

Scenario #1:
3
Scenario #2:
0
Scenario #3:
5
Scenario #4:
0

【题解】

归并排序是将数列a[l,r]分成两半a[l,mid]和a[mid+1,r]分别进行归并排序，然后再将这两半合并起来。在合并的过程中（设l<=i<=mid，mid+1<=j<=r），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数.

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<iostream>
#define M 500500
using namespace std;
int n,T;
int ans;
int a[M],tmp[M];
void Merge(int l,int m,int r)           //统计逆序对
{
	int i=l;
	int j=m+1;
	int k=l;
	while(i<=m&&j<=r)
	{
		if(a[i]>a[j])
		{
			tmp[k++]=a[j++];
			ans+=m-i+1;
		}
		else
		{
			tmp[k++]=a[i++];
		}
	}
	while(i<=m) tmp[k++]=a[i++];
	while(j<=r) tmp[k++]=a[j++];
	for(int i=l;i<=r;i++)
		a[i]=tmp[i];
}
void Merge_sort(int l,int r)            //归并排序
{
	int mid=(l+r)>>1;
	if(l<r)
	{
		Merge_sort(l,mid);
		Merge_sort(mid+1,r);
		Merge(l,mid,r);
	}
}
int main()
{
	scanf("%d",&T);
	for(int t=1;t<=T;++t)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
			scanf("%d",&a[i]);
		Merge_sort(1,n);
		printf("Scenario #%d:\n%d\n\n",t,ans);
		ans=0;
	}
	return 0;
}

6.二分联赛例题之火柴排队（noip2013）

【题目链接】
洛谷【1966】
【题目描述】
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$\sum_{i=1}^n (ai-bi)^2$
其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
【输入格式】
输入文件为 match.in。
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
【输出格式】
输出文件为 match.out。
输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。
【输入样例】

【输入输出样例 1】
4
2 3 1 4
3 2 1 4
【输入输出样例 2】
4
1 3 4 2
1 7 2 4

【输出样例】

【输入输出样例 1】
1
【输入输出样例 2】
2

【题解】
将两盒火柴按从低到高排序并保留其原来的位置，然后把b的位置对应到a的位置上，再对b的位置进行归并排序求逆序对。（贪心策略：从低到高一一对应即为最小距离）

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<iostream>
#include<algorithm>
#define M 500500
using namespace std;
int n,ans;
struct match{
	int hi,pos;            //hi为火柴高度，pos为火柴原本的位置 
}a[M],b[M];               //a，b为两盒火柴 
int t[M],tmp[M];          //t[]w为对应数组，tmp[]为归并排序时的临时数组 
int cmp(match x,match y)
{
	return x.hi<y.hi;     //按从低到高的规则排序 
}
inline void Merge(int l,int m,int r)
{
	int i=l;
	int j=m+1;
	int k=l;
	while(i<=m&&j<=r)
	{
		if(t[i]>t[j])
		{
			tmp[k++]=t[j++];
			ans+=m-i+1;
		}
		else
		{
			tmp[k++]=t[i++];
		}
	}
	while(i<=m) tmp[k++]=t[i++];
	while(j<=r) tmp[k++]=t[j++];
	for(int i=l;i<=r;i++)
		t[i]=tmp[i];
}
inline void Merge_sort(int l,int r)
{
	int mid=(l+r)>>1;
	if(l<r)
	{
		Merge_sort(l,mid);
		Merge_sort(mid+1,r);
		Merge(l,mid,r);
	}
}
int main()
{
	scanf("%d",&n);
	int ta;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&ta);
		a[i].hi=ta;
		a[i].pos=i;
	}
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&ta);
		b[i].hi=ta;
		b[i].pos=i;
	}
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;++i)
		t[a[i].pos]=b[i].pos;     //将b的位置对应到a的位置上 
	Merge_sort(1,n);              //归并排序求逆序对 
	printf("%d",ans);
	return 0;
}

-1.二分放弃

如果你并不能学会二分。。。放弃好了。。。
-the end-撒花*\ (￣▽￣)/~