本人刚开始准备秋招笔试，还没有学数据结构等知识。记录一下吧。
阿里21届内推第一题：n个人乘坐一条船过河，船每次可以载两人，过河时间为体重最大者的体重值，若一人过河，则时间为其体重值。求n个人过河最短时间，需要考虑过河后还要划回来。
输入：第一行为T，代表有几组数据；
第二行为n，代表有多少个人；
第三行为每个人的体重数值；
输出：每行为每组数据的结果。
考虑到过河需要一来一回，首先可推出，至少每次过河回来的那人是体重较小的那个，由此可知，每次回来的，都应该是那个体重最小的人，这样最终总和才会最小。
故，（n>2时）计算方法为从体重最大者一直加到体重第二大者，然后加上体重最小的乘以（n-2）；（n<=2时），一趟即可，按体重最大者计算。
后面根据样例发现该思路是不全面的，但是之前也有类似的题目，看了之后才明白。不过也明显感觉，这类题目，归根到底还是要多刷吧，如果有大量的练习经验应该会好很多。这个帖子也算给自己还有其他正在努力的人加油打气吧！
全部评论
(3) 回帖