【P1809 过河问题】题解

贪心，我们设时间序列为 \(\{a_i\}\)，长度为 \(n\)（先排序 \(\{a_i\}\)）。

分类讨论（其中的「\(1\)」「\(2\)」等均指「速度第 \(1\) 人」「速度第 \(2\) 人」）：

如果 \(n=2\)，那么答案显然是 \(a_2\)。
如果 \(n=3\)，那么答案模拟一下知道是 \(a_1+a_2+a_3\)。
如果 \(n>3\)，那么考虑先处理后面两个最慢的人：
- 让 \(1\) 全揽了，答案显然是 \(2a_1+a_n+a_{n-1}\)（\(1\) 还要往回走啊）；
- 让 \(1,2\) 把船运过去，具体步骤「\(1,2\) 过去，\(1\) 回来候补，\(n,n-1\) 回去，\(1\) 带船过去，和 \(2\) 回来」，同理答案是 \(a_1+2a_2+a_n\)；
把这两个取 \(\min\) 即可。

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

const int N=1e6+5;

typedef long long ll;

int n,a[N];

ll solve(int n)

{

	if (n==2) return a[2];

	if (n==3) return a[1]+a[2]+a[3];

	return solve(n-2)+min(a[1]*2+a[n]+a[n-1],a[1]+a[2]*2+a[n]); // 注意递归项 solve(n-2) 要加上

}

int main()

{

//	freopen("input.in","r",stdin);

	cin>>n;

	for (int i=1;i<=n;i++) cin>>a[i];

	sort(a+1,a+1+n); cout<<solve(n);

	return 0;

}

巴特西

【P1809 过河问题】题解

最新文章

热门文章