问题 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<iostream>
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<<ans<<endl;return 0;
}
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(mid+1,y);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<bits/stdc++.h>
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<n;j++)printf("%3d",matchlist[i][j]);printf("%3d\n",matchlist[i][n]);}
}
int main()
{cin>>n;n=1<<n;makelist(1,1,n,n,1,n);print(n);return 0;
}
问题 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<bits/stdc++.h>
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]<sum)continue;cow++;sum=x[i]+num;}if(cow>=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<<ans<<endl;
}
问题 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<bits/stdc++.h>
#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<<int(r*1000)<<endl;
}