算法设计与分析作业:小朋友过桥问题(蓝桥杯)

2021/10/7 14:11:08

本文主要是介绍算法设计与分析作业:小朋友过桥问题(蓝桥杯),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在一个夜黑风高的晚上,有 nn 个小朋友在桥的这边,现在他们需要过桥,但是由于桥很窄,每次只允许不超过两人通过,他们只有一个手电筒,所以每次过桥后,需要有人把手电筒带回来,第 ii 号小朋友过桥的时间为 a_iai​,两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

输入格式
第一行输入一个整数 nn,表示有 nn 个小朋友。

第二行有 nn 个整数 a_iai​ ,a_iai​ 表示第 ii 个小朋友过河需要的时间。

输出格式
输出一个整数,表示所有小朋友过河所需要的时间。

随后是你的通过和返回次序,每一行是两个或者三个整数,第一个整数,表示这一行有几个整数,后面的一个或者两个整数对应着人(通过时间代表人),返回也要占一行。

数据范围
对于 30%30% 的数据:1 \le n \le 51≤n≤5。

对于 100%100% 的数据:1 \le n \le 10001≤n≤1000 ,0 < a_i \le 10000<ai​≤1000

样例解释
1717 秒

(1,2)(1,2) 22 秒

(1)(1) 11 秒

(5,10)(5,10) 1010 秒

(2)(2) 22 秒

(1,2)(1,2) 22 秒

本题答案不唯一,符合要求的答案均正确

样例输入复制
4
1 2 5 10
样例输出复制
17
2 1 2
1 1
2 5 10
1 2
2 1 2

解题思路:
1.如果人数小于二,一起都走过去(时间只加较大的那个)
2.如果人数大于二,且人数为偶数:
先将第一个人与第二个人安排过去,后面的丛小到大排序,每一个相邻两人作为一组,每组需要第一个与第二个人走回来:
具体为第一个人先走回来,这一组走过去(时间加两者中大的那个),第二个人在走回来,第一个人与第二个人一起走过去。
进行n/2-1次将吧后面的所有组都安排过去。
3.如果人数大于二,且人数为奇数,将时间最长的人先剔出来,剩余人数为偶数个(此时可以用上面2.的思路直接做出来),剩下最后那个时间最长的那个人直接让一回来接一遍就行。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5+100;
int a[maxn];
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    if(n<=2)
    {
        cout<<a[n-1]<<endl;
        return 0;
    }
    bool flag=0;
    if(n&1)//如果人数为奇数先将最后那个人剔出来。
    {
        flag=1;
        n--;
    }
    ll sum=0;
    sum+=a[1];//第一个与第二个人先过去
    for(int i=2;i<n;i+=2)//每次讲两个人送过去。
    {
    	sum+=a[0];//第一个人先送回手电筒来,
        sum+=a[i+1];//这一组一起过去。
        sum+=a[1]+a[1];//第二个人把手电送回来,和第一个人一起过去。
    }
    if(flag)//剩下最后那个人让第一个人回来接一遍就行啦。
    {
        sum+=a[0];
        sum+=a[n];
    }
    cout<<sum<<endl;
    return 0;
}



这篇关于算法设计与分析作业:小朋友过桥问题(蓝桥杯)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程