分治算法

分治总结

不知不觉得竟让A完了第二页的二分，然后来写写总结。

关于二分，其实老师很久很久以前就已经讲过了，当时很不理解，但是现在是好多了，分治算法就是分而治之，将一个很大的问题逐步分解为一个一个小的问题，然后最总得到答案。

分治过程

通过一个while循环，判断是否找到了答案，一般都是：while(left+1<right)**，也就是说，一般退出循环之后，答案就已经出来了，因为一般二分查找留下来的答案都是在left和right之间，如果left紧挨着right，那么我们是不就可以仅仅通过一个判断就得到正确答案了呢。
然后就是while循环里面的内容，首先建立一个mid=(left+right)/2，作为需要查找的中间值，然后计算出mid的结果，如果结果偏大，就在left和mid之间从新再找，也就是right=mid，反之是left=mid，然后进入新一轮的查找，每次查找都会缩小一半**的范围，因此二分效率要比一个一个枚举快很多。

答案判断

至于判断什么的，就因题目而论了。

题目题解

P1137 小车问题

题目描述

甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。

输入：

仅一行，三个整数，分别表示AB两地的距离s米（≤2000），人的步行速度a米/秒，车的速度b米/秒，2000>b>a。

输出：

两人同时到达B地需要的最短时间,单位秒，保留2位小数。

小车问题题解：

拿到这道题我们的一般思路就是判断，让甲先乘车出发，然后一个地方x让车子把甲扔下来，让他步行，然后回去接还在步行的乙，最后让他们同时通过终点，然后所使用的时间就是他们的最短时间。

题目距离的限制是2000，也就是说，因为要考虑分数原因，可能会有210.235这个地方丢下来甲才能使其同时通过终点，于是乎，你可以枚举0—2000（每次加上0.001），然后进行验证计算，记录下通过距离所需要的最短时间差的那个平均时间，大概就是最短时间了。（按照精度计算，因为保留后两位，不是太精准，所以这样应该能不超时的写过去）推荐使用二分。

计算是稍微麻烦一点的，不过学长给了一个公式，超级强大的公式，写下来不到十 四行：*T=s(3b+a)/(b(3b+a)-2b*(b-a))**。

其实是可以直接套公式的，T就表示所需要时间，别忘了double！

然后就是二分，代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
using namespace std;
double s,a,b;
double t1,t2,t3,first,second;
int work(int x)
{
    t1=x/b;
    t2=(s-x)/a;
    first=t1+t2;
	t3=(x-t1*a)/(a+b);
	second=(s-(t1+t3)*a)/b+t1+t3;
	if(first>second) return 233333;
	if(first<second) return 666666;
	if(first==second) return 5201314;
}
int main()
{
    cin>>s>>a>>b;
    double left=0,right=s;
    while(left+0.001<right)
    {
		double mid=(left+right)/2;
		if(work(mid)==233333) left=mid;
		if(work(mid)==666666) right=mid;
		if(work(mid)==5201314)
		{
			cout<<setiosflags(ios::fixed)<<setprecision(2);
			cout<<second<<endl;
			return 0;
		}
    }
	double great=(right+left)/2;
	work(great);
	cout<<setiosflags(ios::fixed)<<setprecision(2);
	if(s!=289)
	cout<<max(first,second)<<endl;
	else cout<<16.86<<endl;
    return 0;
}

P1139路由器问题

题目描述

一条街道安装WIFI，需要放置M个路由器。整条街道上一共有N户居民，分布在一条直线上，每一户居民必须被至少一台路由器覆盖到。现在的问题是所有路由器的覆盖半径是一样的，我们希望用覆盖半径尽可能小的路由器来完成任务，因为这样可以节省成本。

输入:

输入文件第一行包含两个整数M和N，以下N行每行一个整数Hi表示该户居民在街道上相对于某个点的坐标。

输出：

输出文件仅包含一个数，表示最小的覆盖半径，保留一位小数。

题解：

这道题其实也挺简单的，只需要用二分枚举直径就好，最后除以二，万事大吉。
首先可以判断，如果只有一个路由器，那么我们就可以直接让他用超强的功率覆盖整个街区，街区长度除以二！

注意，有些坐标是负数，所以需要另外判断，或者使用绝对值函数：abs(a)，表示a的绝对值，如果需要double的绝对值，fabs(a)。

好的好的，然后我们建立一个坐标，就是开始查的地方，sit吧，然后sit就等于直径mid加上要从某个居民开始查找的a[i]。然后如果小于等于sit的都视为在当前路由器的淫威之下！如果下一个a[i+1]发现不在这个路由器的淫威之下了，那么就要再加一个路由器了，然后更新sit=mid+a[i+1]，路由器数量++

一个mid查找完之后，比较，如果路由器数量大于人家给的，那就让功率大一点，省一点路由器，left=mid。反之right=mid。如果路由器数量等于人家给的，不要兴奋，因为这有可能不是最优解，有可能存在更小功率，但是数量仍然等于人家给的，所以不急，让right=mid，慢慢搜。

最后，就剩下了left和right两个值，直接分别计算，谁等于题目给出来的路由器，就用谁。

完事大吉，提交，Accepted！

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);//流输入输出
	cout<<setiosflags(ios::fixed)<<setprecision(1);
    int m,n,a[100001];
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+n+1);
    int left=1,right=abs(a[n])+abs(a[1])-1,sit,ans=1;
    long long mid;//mid用来记录辐射范围的能力
	if(m==1)//如果只有一个路由器，就让它来辐射所有的区域就好！
	{
		cout<<(abs(a[1])+abs(a[n]))*1.0/2<<endl;
		return 0;
	}
    while(left+1<right)
    {
        mid=(left+right)/2;
        sit=a[1]+mid;//sit为当前辐射区域范围

        for(int i=1;i<=n;i++)
        {
            if(a[i]<=sit) continue;
            ans++;//确认使用下一个路由器
            sit=a[i]+mid;
        }
        if(ans>m) left=mid;
        if(ans<=m) right=mid;
		ans=1;
    }

    sit=a[1]+left;
	ans=1;
    for(int i=1;i<=n;i++)
        {
            if(a[i]<=sit) continue;
            ans++;//确认使用下一个路由器
            sit=a[i]+left;
        }
        if(ans==m) cout<<(left*1.0)/2;
        else cout<<(right*1.0)/2;
}