首页 > 其他分享 >问题 G: 过桥问题

问题 G: 过桥问题

时间:2022-11-11 18:34:42浏览次数:40  
标签:sum 过去 整体 手电筒 问题 过桥 搬运

准确来说这题是一道贪心题目。
可能确实有些难度,但具体分析后就不难了。首先我们就先看看样例吧,其实可能会有人连样例都看不懂哈哈哈哈哈

题解有点长要细心看哦

(第一整体!!!)五个人分别需要1 3 6 8 12分钟才能过桥,先说29这个答案是怎么来的。我们先让1 3两个人过桥用了3min,然后1把手电筒拿回来,共计4min,再8 12(因为只记最大时长,所以我们要把时长最大的两个人先运过去,这样8分钟的这个人就不用算上时间啦)过桥共计16min,这时候需要个人把手电筒拿回来,这就是我们刚刚为什么要把3运过去的原因了,因为他把手电筒拿回来所需的时间是最短的(因为1在第一次过桥的时候要把手电筒拿回来,所以这次只能是倒数第二小的3将其拿回来),这时候总计19min。
这时候再看还剩下谁 1 3 6,发现1 3为了运手电筒回来了,而最大的8和12过桥了,所以我们可以把这一次搬运视为一个整体。也就是让最小的两个过桥先把一个人运过去(运过去的用处是可以更快的把手电筒拿回来),然后让此时最大的两个人过桥,再让倒数第二小的人(即刚刚被运过去的人)把手电筒带回来。

(第二整体!!!)再看第二部分,这时候只有三个人1 3 6,很明显我们先把1 6送过去,总计25min,再让1回来,总计26min,最后让1 3过去,总计29min.我们得到了样例的答案,那么1 3 6三个人的搬运也可一视为一个整体,这时候不需要特意运一个人过去来搬运手电筒,我们可以让1来回跑(能者多劳),这样就可以把三个人都运过去了。
最后也就是这道题只有两种情况:1、让两个时间最小的人把两个时间最大的人搬运过去。2、让一个时间最短的人把两个时间最大的人搬运过去。
最后总结一下,如果只有两个人,那么过桥时间就是耗时较长的那个人的时间,如果只有三个人,那么就如样例里的第二个整体一样,如果有五或者更大的奇数就可以先按照样例中的第一个整体来,会发现每次减少的是两个人,最后就只剩下三个人,那么就是第二整体。在比如四或者更大的偶数,一开始也可以运用第一整体的方法一直减少人数,直到最后肯定只剩下两个人,那么两个人过桥时间也显而易见了。

上代码!!!

点击查看代码
#include<stdio.h>

#include <algorithm>

using namespace std;

int main()
{
    int n, a[1005], i, j, sum;
    while (scanf("%d", &n) != EOF)
    {
        sum = 0;//不要忘记归零哦
        for (i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);//排序,当然也可以用冒泡选择插入啦,只是sort比较方便而已
        while (n > 1)
        {
            if (n == 2)//最后只剩下两个人
            {
                sum += a[1];
                break;
            }
            else if (n == 3)//最后只剩下三个人(第二整体)
            {
                sum += a[0] + a[1] + a[2];
                break;
            }
            else
            {
                sum += a[1] + a[0] + a[n - 1] + a[1];//也就是第一整体的搬运
                n -= 2;
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}
/*嘿嘿
在这里预祝zyy女士生日快乐

标签:sum,过去,整体,手电筒,问题,过桥,搬运
From: https://www.cnblogs.com/myy-zzb/p/16881419.html

相关文章