暑假集训测试（二）题解

1题、货运神器

　模拟算法：分析从 a 到 b 有三种方式：

　　1) a -> b ，时间为：t1 = |b-a|
　　2) a->x->y->b，时间为：t2 = |x-a|+|b-y|
　　3) a->y->x->b，时间为：t3 = |y-a|+|b-x|

　则 Ans=min(t1, t2, t3)

2题、错误信息

　设 x[1]..x[n] 读入n条信息的x，也是旺财藏身的所有可能的位置
　设 a[1]..a[na] 表示说 >=x 的数据，
　设 b[1]..b[na] 表示说 <=x 的数据，

　100分解法：排序+枚举+查找算法：

　1)、将3个数组均由小到大排序；

　2)、枚举旺财可能藏身的位置：x[1],x[2],……x[n]

　　● 假设狗藏在 x[k] 这个位置，则按下面方法计算此时错误信息数：
　　● 在a[1]..a[na]中查找有多少个元素大于x[k]，假设有s1个（不正确数）；
　　● 在b[1]..b[nb]中查找有多少个元素小于x[k]，假设有s2个（不正确数）；
　　●所以Ans=min(Ans,s1+s2)

　　至于查找：可以用二分查找，也可以利用单调性，用不回头顺序查找优化！

　　时间复杂度：
　　　不回头顺序查找：O(n+n)
　　　二分查找：O(nlogn)

3题、关押罪犯

　一、40分解法：

　两重循环枚举新罪犯安置的牢房i,j，每枚举一种，就计算距离最近的两个罪犯的距离。
　最后的答案是所有最近的距离中选择一个最大的。　
　时间复杂度O(n^3)

　二、100分解法：二分答案（最小值最大）+ 贪心策略

　设有cnt个罪犯，他们所在牢房的编号为：x[1]..x[cnt]（由小到大有序），可以在输入数据时统计。

　1)、特判： 若cnt=0，则答案为 N-1。

　2)、若 cnt>0 ，则二分猜：加入新罪犯后，罪犯之间的最小距离。

　　●答案范围：l=1，r=初始时罪犯之间的小距离

　　●验证猜的mid是否可行，贪心策略：验证函数：bool check(mid) 在保证罪犯之间距离不小于mid的情况下，
　　最多能加入新罪犯的数量；

　时间复杂度：O(nlogn)

4题、跨国旅游

　贪心算法：

　设 x[0]=0 是出发点，x[N+1]=L 是终点，终点的油价：p[N+1]=0;

　1)、特判：无解判断，若x[1]-x[0]>B 以及 x[i]-x[i-1]>V(i=2~N+1) ，则无解！

　2)、当有解时：

　　　开始：从 x[0] 到 x[1]，油箱中剩余油量为 B = B - ( x[1] - x[0] )。

　　　枚举油站 i=1,2,3,…N ，设已经行驶到油站 i，且邮箱中剩余油量为B，用贪心策略决策在 i 站加油数量：

　　　在 p[i+1] ~ p[N+1] 中查找第一个油价小于等于 p[i] 的加油站 j， 此时有如下几种情况：

　　　● 情况1：若 x[j]-x[i] <= B，说明剩余油量可以行驶到 j， 因此 i 点不用加油，行驶到 j 的剩余
　　　　油量为：B = B-(x[j]-x[i])，i = j；

　　　● 情况2：若 x[j]-x[i] > B 且 x[j]-x[i] < V：则需要在 i 点加 (x[j]-x[i]-B) 单位的油，费用
　　　　为：p[i]*(x[j]-x[i]-B)，行驶到 j 点剩余油量 B = 0, i = j；

　　　● 情况3：x[j]-x[i] >= V：则在 i 点把油箱加满，即加（V-B）单位的油，费用为：p[i] * (V-B)，然后行
　　　　驶到第i+1个站的剩余油量 B = V-(x[i+1]-x[i]) ，i = i+1。

　　　最后的答案就是所有站点加油的费用总和。