2019年寒假强化训练：二分算法深度解析与实战演练

问题 A: 【递归】二分查找

题目描述

用递归算法实现二分查找，即：有n个已经从小到大排序好的数据（不重复），从键盘输入一个数X，用对半查找方法，判断它是否在这n个数中。

输入

第一行，正整数n，N<=105；

第二行，n个整数（int范围内，不重复），中间用空格分隔；

第三行，整数X。

输出

如果找到X，输出其位置；否则输出-1。

样例输入

10
10 20 30 40 50 60 70 80 90 100
90

样例输出

9

代码：

#include
using namespace std;
int ans=-1;
int a[100005];
int b,n;
void find(int,int);
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>b;find(1,n);cout<}
void find(int x,int y)
{int mid=(x+y)/2;if(a[mid]==b) {ans=mid;return;} else if(x>y)return;else {if(a[mid]b)find(x,mid-1);}
}

问题 C: 循环比赛日程表

题目描述

设有n个选手进行循环比赛，其中n = 2^m，要求每名选手要与其他n - 1名选手都赛一次，每名选手每天比赛一次，循环赛共进行n - 1天，要求每天没有选手轮空。

输入

一行，包含一个正整数m。( 1 <= m <= 10)

输出

表格形式的比赛安排表（n行n列），每个选手的编号占三个字符宽度，右对齐。

样例输入

3

样例输出

1 2 3 4 5 6 7 82 1 4 3 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 8 7 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1

题解：

分治算法

以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。

#include
const int MAXN=65;
using namespace std;
int n,matchlist[MAXN][MAXN];
void makelist(int a1,int b1,int a2,int b2,int x,int y)
{if(x==y)matchlist[a1][b1]=x;else{int a3=(a1+a2)/2;int b3=(b1+b2)/2;int xy=(x+y)/2;makelist(a1,b1,a3,b3,x,xy);makelist(a1,b3+1,a3,b2,xy+1,y);makelist(a3+1,b1,a2,b3,xy+1,y);makelist(a3+1,b3+1,a2,b2,x,xy);}
}
void print(int n)
{for(int i=1;i<=n;i++){for(int j=1;j}
int main()
{cin>>n;n=1<}

问题 D: 愤怒的牛

题目描述

原题来自：USACO 2005 Feb. Gold

农夫约翰建造了一座有 nn 间牛舍的小屋，牛舍排在一条直线上，第 ii 间牛舍在 x_ixi 的位置，但是约翰的 mm 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？ 

输入

第一行用空格分隔的两个整数 n 和 m； 

第二行为 n个用空格隔开的整数，表示位置 xi。  

输出

输出仅一个整数，表示最大的最小距离值。

样例输入

5 3
1 2 8 4 9

样例输出

3

样例解释

把牛放在 1, 4 ,8这样最小距离是 3 。 

题解：

二分两头牛之间的最小的最大距离，然后在check函数中检查答案是否合法

代码：

#include
const int MAXN=100005;
using namespace std;
int n,m;
int x[MAXN];
int check(int num)
{int cow=1,sum=x[1]+num;for(int i=2;i<=n;i++){if(x[i]=m)return 1;else return 0;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)cin>>x[i];sort(x+1,x+1+n);int mid,l=0,r,ans;r=x[n]-x[1];while(l<=r){mid=(l+r)/2;if(check(mid)==1){l=mid+1;ans=mid;}else r=mid-1;}cout<}


问题 E: Best Cow Fences

题目描述

原题来自：USACO 2003 Mar. Green

给定一个长度为 n 的非负整数序列 A，求一个平均数最大的，长度不小于 L 的子段。 

输入

第一行用空格分隔的两个整数 n和 L； 

第二行为 n个用空格隔开的非负整数，表示 Ai。 

输出

输出一个整数，表示答案的 10001000 倍。不用四舍五入，直接输出。

样例输入

10 6
6 4 2 10 3 8 5 9 4 1

样例输出

6500

题解：

二分+前缀和优化

二分一个平均数，然后检查答案

怎么检查答案：

如果一个子串的平均数大于二分的平均数，那么可以理解为找到一个子串，

子串的和非负，可以用前缀和优化一下

代码：

#include
#define INF 1<<30
using namespace std;
int n,L;
double a[100010],sum[100010];
bool check(double mid)
{for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-mid;double minn=INF,ans=-INF;for(int i=L;i<=n;i++){minn=min(minn,sum[i-L]);ans=max(ans,sum[i]-minn);}return ans>=0.0;
}
int main()
{cin>>n>>L;memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++) cin>>a[i];double l=-1e6,r=1e6;while(r-l>1e-5){double mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;}cout<}