一、编程题
1、1.开餐馆
北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ... mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。
时间限制：1000
内存限制：65536
输入
标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行, 第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000). 第2行:n 个地点的位置m1 , m2, ... mn ( 1000000 > mi > 0 且为整数,升序排列) 第3行:n 个地点的餐馆利润p1 , p2, ... pn ( 1000 > pi > 0 且为整数)
输出
对于每组测试数据可能的最大利润
样例输入
```
2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30
```
样例输出
```
40
30
```
参考答案：
略
解析：【喵呜刷题小喵解析】这个问题可以使用动态规划解决。我们可以定义一个长度为n+1的数组dp，其中dp[i]表示前i个地点能够获得的最大利润。对于每个地点i，我们可以选择开设餐馆或者不开设餐馆。如果选择开设餐馆，那么餐馆的位置必须是i，并且餐馆的利润是p[i]，但是餐馆之间的距离必须大于k，所以餐馆的位置必须在[max(0, i-k-1), i-1]这个范围内，并且这个范围内不能开设餐馆，所以利润是dp[max(0, i-k-1)] + p[i]。因此，状态转移方程为dp[i] = max(dp[i-1], dp[max(0, i-k-1)] + p[i])。最后返回dp[n]即可。在代码中，我们首先读入测试数据的组数t，然后对于每组测试数据，读入地点总数n，距离限制k，地点的位置m和餐馆的利润p，然后调用max_profit函数计算最大利润，并输出。
2、2.糖果
由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多少糖果呢？ 注意：Dzx只能将糖果公司的产品整件带走。
时间限制：7000
内存限制：65536
输入
第一行包含两个整数N(1<=N<=100)和K(1<=K<=100) 以下N行每行1个整数，表示糖果公司该件产品中包含的糖果数目，不超过1000000
输出
符合要求的最多能达到的糖果总数，如果不能达到K的倍数这一要求，输出0
样例输入
```
5 7
1
2
3
4
5
```
样例输出
```
14
```
提示
Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。
参考答案：
略
解析：【喵呜刷题小喵解析】本题要求Dzx选择若干件糖果公司的产品，使得选择的糖果总数是K的倍数，且总数最多。我们可以采用贪心算法来解决这个问题。首先，我们将糖果公司的N件产品按照包含的糖果数量从大到小排序。然后从最大的产品开始累加，直到总数达到K的倍数为止。这样可以保证在满足K的倍数条件的基础上，总数尽可能多。具体的算法如下：1. 读取输入数据，得到N和K的值，以及N件产品包含的糖果数量。2. 对N件产品按照糖果数量从大到小排序。3. 初始化总糖果数量为0，计数器count为0。4. 从最大的产品开始累加，更新总糖果数量。如果总糖果数量是K的倍数，记录当前的产品数量count，并跳出循环。5. 如果count为0，说明无法选择到满足K的倍数的产品，输出0。6. 否则，输出选择的产品列表和总糖果数量。在本题的示例输入中，N=5，K=7，糖果公司包含的产品数量分别为1、2、3、4、5。我们按照糖果数量从大到小排序后得到5、4、3、2、1。然后从最大的产品5开始累加，得到总糖果数量为15，不是7的倍数。接着累加产品4，得到总糖果数量为14，是7的倍数，且总数最多。因此，输出14。
3、3.鸡蛋的硬度
最近XX公司举办了一个奇怪的比赛：鸡蛋硬度之王争霸赛。参赛者是来自世 界各地的母鸡，比赛的内容是看谁下的蛋最硬，更奇怪的是XX公司并不使用什么精密仪器来测量蛋的硬度，他们采用了一种最老土的办法--从高度扔鸡蛋--来 测试鸡蛋的硬度，如果一次母鸡下的蛋从高楼的第a层摔下来没摔破，但是从a+1层摔下来时摔破了，那么就说这只母鸡的鸡蛋的硬度是a。你当然可以找出各种 理由说明这种方法不科学，比如同一只母鸡下的蛋硬度可能不一样等等，但是这不影响XX公司的争霸赛，因为他们只是为了吸引大家的眼球，一个个鸡蛋从100 层的高楼上掉下来的时候，这情景还是能吸引很多人驻足观看的，当然，XX公司也绝不会忘记在高楼上挂一条幅，写上“XX公司”的字样--这比赛不过是XX 公司的一个另类广告而已。
勤于思考的小A总是能从一件事情中发现一个数学问题，这件事也不例外。“假如有很多同样硬度的鸡蛋，那么我可以用二分的办法用最少的次数测出鸡蛋 的硬度”，小A对自己的这个结论感到很满意，不过很快麻烦来了，“但是，假如我的鸡蛋不够用呢，比如我只有1个鸡蛋，那么我就不得不从第1层楼开始一层一 层的扔，最坏情况下我要扔100次。如果有2个鸡蛋，那么就从2层楼开始的地方扔……等等，不对，好像应该从1/3的地方开始扔才对，嗯，好像也不一定 啊……3个鸡蛋怎么办，4个，5个，更多呢……”，和往常一样，小A又陷入了一个思维僵局，与其说他是勤于思考，不如说他是喜欢自找麻烦。
好吧，既然麻烦来了，就得有人去解决，小A的麻烦就靠你来解决了：）
时间限制：1000
内存限制：65536
输入
输入包括多组数据，每组数据一行，包含两个正整数n和m(1<=n<=100,1<=m<=10)，其中n表示楼的高度，m表示你现在拥有的鸡蛋个数，这些鸡蛋硬度相同（即它们从同样高的地方掉下来要么都摔碎要么都不碎），并且小于等于n。你可以假定硬度为x的鸡蛋从高度小于等于x的地方摔无论如何都不会碎（没摔碎的鸡蛋可以继续使用），而只要从比x高的地方扔必然会碎。 对每组输入数据，你可以假定鸡蛋的硬度在0至n之间，即在n+1层扔鸡蛋一定会碎。
输出
对于每一组输入，输出一个整数，表示使用最优策略在最坏情况下所需要的扔鸡蛋次数。
样例输入
```
100 1
100 2
```
样例输出
```
100
14
```
提示
最优策略指在最坏情况下所需要的扔鸡蛋次数最少的策略。 如果只有一个鸡蛋，你只能从第一层开始扔，在最坏的情况下，鸡蛋的硬度是100，所以需要扔100次。如果采用其他策略，你可能无法测出鸡蛋的硬度(比如你第一次在第二层的地方扔,结果碎了,这时你不能确定硬度是0还是1)，即在最坏情况下你需要扔无限次，所以第一组数据的答案是100。
参考答案：
略
解析：【喵呜刷题小喵解析】这是一个关于二分查找策略的问题，题目中描述了一个场景：在不知道鸡蛋硬度的前提下，需要通过有限次数的实验来确定鸡蛋的硬度。这里的策略就是二分查找。二分查找的核心思想是每次通过测试鸡蛋从楼层的中间高度摔下来是否破碎，来确定鸡蛋的硬度是在上半部分还是下半部分。通过不断缩小搜索范围，最终确定鸡蛋的硬度。在这个问题中，二分查找的应用稍微有些不同。因为鸡蛋的硬度是未知的，而且每次实验都会消耗一个鸡蛋，所以我们需要尽可能地减少实验次数。根据题目，当只有一个鸡蛋时，我们只能从第一层开始一层一层地尝试，最坏情况下需要尝试100次。当有多个鸡蛋时，我们可以从楼层的中间高度开始尝试，如果鸡蛋破碎，说明硬度在上一层，否则在下一层。通过这种方式，我们可以尽可能地减少实验次数。算法的具体实现是：首先，将搜索范围从1到n（楼的高度）进行二分。然后，根据当前的鸡蛋数量m和中间值mid，决定是继续二分搜索还是减少鸡蛋数量并调整搜索范围。最后，输出在最坏情况下所需要的扔鸡蛋次数。这个算法的时间复杂度是O(log n)，其中n是楼的高度。在最坏情况下，需要尝试的次数是n，即输出结果为n。
4、4.山区建小学
政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
时间限制：24000
内存限制：65536
输入
第1行为m和n，其间用空格间隔 第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。 例如 10 3 2 4 6 5 2 4 3 1 3 表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。
输出
各村庄到最近学校的距离之和的最小值。
样例输入
```
10 2
3 1 3 1 1 1 1 1 3
```
样例输出
```
18
```
参考答案：
略
解析：【喵呜刷题小喵解析】这个问题可以使用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示前i个村庄中选择j个村庄建小学，使得所有村到最近小学的距离总和最小的值。对于dp[i][j]，我们可以考虑两种情况：1. 在第i个村庄建小学，那么前i-1个村庄中选择j-1个村庄建小学，即dp[i-1][j-1]。此时，第i个村庄到最近小学的距离为0，前i-1个村庄到最近小学的距离为dp[i-1][j-1]。因此，dp[i][j] = dp[i-1][j-1]。2. 不在第i个村庄建小学，那么前i个村庄中选择j个村庄建小学，即dp[i-1][j]。此时，第i个村庄到最近小学的距离为dists[i-1]，前i-1个村庄到最近小学的距离为dp[i-1][j]。因此，dp[i][j] = dp[i-1][j] + dists[i-1]。我们需要在这两种情况中选择一个较小的值作为dp[i][j]的值。最终，dp[m][n]即为所求的答案。以上即为使用动态规划解决该问题的思路。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
