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++详解
145 0
|
存储 人工智能 测试技术
十四届蓝桥杯模拟赛第三期(二)
十四届蓝桥杯模拟赛第三期
134 0
第14届蓝桥杯模拟赛 第2期
请找到一个大于 2022 的最小数,这个数转换成二进制之后,最低的 6 个二进制为全为 0 。请将这个数的十进制形式作为答案提交。
|
算法 程序员 测试技术
【算法集训 | 暑期刷题营】8.1题---线性dp
【算法集训 | 暑期刷题营】8.1题---线性dp
【算法集训 | 暑期刷题营】8.1题---线性dp
|
机器学习/深度学习 人工智能 BI
蓝桥杯真题31日冲刺国一 | 每日题解报告 第二十七天
大家好 我是泡泡 倒数六天 蓝桥开赛!记得打印准考证!
117 0
蓝桥杯真题31日冲刺国一 | 每日题解报告 第二十七天
|
测试技术
2022 第十四届蓝桥杯模拟赛第一期(题解与标程)(下)
2022 第十四届蓝桥杯模拟赛第一期(题解与标程)
487 0
2022 第十四届蓝桥杯模拟赛第一期(题解与标程)(下)
蓝桥杯历届试题 蚂蚁感冒(模拟版+非模拟版)
长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。   每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒。   当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。   这些蚂蚁中,有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。   请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。 输入格式   第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。   接着的一行是n个用空格分开的整数 Xi (-100< Xi < 100), Xi的绝对值, 表示蚂蚁离开杆子左边端点的距离。正值表示头朝右,负值表示头朝左, 数据中不会出现0值,也不会出
205 1
蓝桥杯历届试题 蚂蚁感冒(模拟版+非模拟版)
|
测试技术
2021年第十二届蓝桥杯模拟赛(第四期)题目和解析
蓝桥杯是指蓝桥杯全国软件和信息技术专业人才大赛。是由工业和信息化部人才交流中心举办的全国性IT学科赛事。共有北京大学、清华大学、上海交通大学等全国1200余所高校参赛。
201 0
2021年第十二届蓝桥杯模拟赛(第四期)题目和解析
下一篇
无影云桌面