2013蓝桥杯【模拟赛】运送马匹

简介:

运送马匹
  有1个人,要把n匹马从A村运往B村。
  初始时,人和马都在A村。每次骑1匹马牵1匹马,回来时骑1匹马。
  已知每匹马从A村到B村需要的时间(数字越大越慢)
  两匹马同行时只能迁就较慢者。
  求所有马匹都运到B村的最小的运输时间(此时,人和马都在B村)。
  程序首先输入一个整数n(n<100),表示有n匹马。
  接着是n行整数,表示马从A村到B村的所用的分钟数(小于1000)
  程序输出:1个整数,表示所有马匹均运到B村的最小总耗时。
  例如,
输入:
3
1
2
4
程序应输出:
7
输入:
4
1
4
2
5
程序应该输出:
12
对于编程题目,要求选手给出的解答完全符合ANSI C++标准,不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
代码中允许使用STL类库,但不能使用MFC或ATL等非ANSI c++标准的类库。例如,不能使用CString类型(属于MFC类库)。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意选择自己使用的编译环境。

 


思路:选择两匹最快的马匹来回运送其它的马匹,最后的最后再将这两批最快的马匹运回就完成了
因为用到贪心思想,所以一开始要将马匹的速度从小到大排序,得到速度最快的前两个马匹,之后
运用递归的方法来运送马匹,一回合用最快的马运送两个(例如:1,2,5,4,8:排序后:1,2,4,5,8;先用1,2,将1送到目的地,用时a[1],2返回
,用时a[1],之后速度倒数第二的马匹和速度倒数第一的马匹一起过去,用的时间是a[n-1](此时B地有马3匹,分别是1和a[n-2]和a[n-1]),
之后1再回去,用时a[0],一回合的用时就是a[1]*2+a[0]+a[n-1],此时运送了两匹马(a[n-2]和a[n-1])),直到运送完毕

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[200],sum=0;
int Fun(int n)
{
    if(n==1)
    sum+=a[0];
    else if(n==2)
    sum+=a[1];
    else if(n==3)
    sum+=a[1]+a[2];
    else
    {
        sum+=2*a[1]+a[0]+a[n-1];//每一回合的式子
        Fun(n-2);//运好两匹马之后递归   
    }
}
int main()
{
    int i,j,n,m1,m2;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    sort(a,a+n);//排序(从小到大)
    Fun(n);
    printf("%d\n",sum);
    return 0;
}


 

相关文章
|
5月前
|
算法
详细解读7.2模拟赛
详细解读7.2模拟赛
14 0
|
6月前
|
存储 人工智能 测试技术
2020年第十一届蓝桥杯模拟赛解题报告
2020年第十一届蓝桥杯模拟赛解题报告
|
6月前
|
人工智能 测试技术 C++
蓝桥杯15届第二次模拟赛C/C++详解
蓝桥杯15届第二次模拟赛C/C++详解
144 0
|
6月前
滑雪(蓝桥模拟赛的题)
滑雪(蓝桥模拟赛的题)
56 0
|
11月前
滑雪(也是蓝桥模拟赛的题)
和蓝桥杯模拟赛的最大连通过差不多一个思想
47 0
|
算法
十四届蓝桥杯模拟赛第三期(一)
十四届蓝桥杯模拟赛第三期
440 0
|
存储 人工智能 测试技术
十四届蓝桥杯模拟赛第三期(二)
十四届蓝桥杯模拟赛第三期
134 0
第14届蓝桥杯模拟赛 第2期
请找到一个大于 2022 的最小数,这个数转换成二进制之后,最低的 6 个二进制为全为 0 。请将这个数的十进制形式作为答案提交。
|
存储 机器学习/深度学习 人工智能
【蓝桥杯集训·周赛】AcWing 第 95 场周赛
文章目录 第一题 AcWing 4873. 简单计算 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4874. 约数 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4875. 整数游戏 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
109 0
|
存储 人工智能 算法
【蓝桥杯集训·最后一次周赛】AcWing 第 97 场周赛
文章目录 第一题 AcWing 4944. 热身计算 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4945. 比大小 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4946. 叶子节点 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
128 0