DOJ-team-match 7-过河问题
先模拟一下样例
1
2
5
10
- 1和2去，耗时2
- 1回，耗时3
- 5和10去，耗时13
- 2回，耗时15
- 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;
}