分治算法+P1137小车问题+P1139路由器安置

分治算法

分治总结

不知不觉得竟让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
#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;
}