[Deeplearning] 过河问题

先模拟一下样例

1
2
5
10

1. 1和2去，耗时2
2. 1回，耗时3
3. 5和10去，耗时13
4. 2回，耗时15
5. 1和2去，耗时17

现在我们把题目化为两种策略

策略1：共2人，一起过河，用时较小的将手电筒放回

策略2：共4人，耗时较小的两人先过，接着将手电筒送回，用时较大的两人过，最后右侧用时最小的人将手电筒送回，左侧两人一起过河，耗时最小者将手电筒送回。

最终只需要比较两种策略的用时即可

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,sum = 0;
	cin>>n;
	vector<int>v(n,0);
	for (int i=0;i<n;i++)
		cin >> v[i];
	sort(v.begin(), v.end());
	int i;
	for (i=n-1;i>2;i-=2)
	{
		if (v[i-1]+v[0]>v[1]*2) sum+=v[1]*2+v[0]+v[i];
		else sum+=v[i-1]+v[0]*2+v[i];
	}
	if (i == 2) sum+=v[2]+v[0]+v[1];
	else if(i == 1) sum+=v[1];
	else sum += v[0];
	cout<<sum<<endl;
	return 0;
}