准确来说这题是一道贪心题目。
可能确实有些难度,但具体分析后就不难了。首先我们就先看看样例吧,其实可能会有人连样例都看不懂哈哈哈哈哈
题解有点长要细心看哦
(第一整体!!!)五个人分别需要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