首页 > 代码库 > 【POJ1700】Crossing River 贪心,附贪心问题的一系列详细解析

【POJ1700】Crossing River 贪心,附贪心问题的一系列详细解析

题意:一群人过河,船每次只能装两人,每次过河时间为两人权值较大的那个。

题解:

    这种题的贪心策略往往不是很好想,这个时候我们就需要依照尽量逼近正解的思路,进行多种贪心,在每种贪心都保证正确的前提下,取多个答案的最值,这样往往就是正解,而即便可以卡,数据也很难出,并不是写个rand+debug拍上两个小时就能拍出来的。

    而这种 多线程贪心 可以有两种:

一、单独做每种,然后取最优。

二、每一步转移都用多种贪心取得,然后直接取最后的状态值。


显然后一种的正确性比较高,但是往往因为“贪心”的奇葩性,而并不能写出这样的贪心。

而本题恰好可以用后一种贪心。


另外要说一下,就是这道题的贪心的方向有二:

一、每次过河的时间尽量小

二、过河的次数尽量少。

这样就又满足了一个性质,就是影响答案的几种条件都可以有针对策略时,我们将它们都进行选择,然后再加一些在几种条件之间进行妥协的策略,即牺牲某条件,迎合另一个条件的一系列策略。这样基本就是,或者说就已经是绝对正确的代码了。


而本题的两种策略则是

一、耗时最短的人一直在船上来回送人

二、耗时最短的来回送船,然后俩耗时最长的一起走。(实现:最短送船回来,俩人过去,次短来接最短过岸)


好了,贴代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1005
using namespace std;
int a[N],f[N],n;
int main()
{
//	freopen("test.in","r",stdin);
	int i,g;
	int ta,tb;
	scanf("%d",&g);
	while(g--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		f[1]=a[1],f[2]=a[2];
		for(i=3;i<=n;i++)
		{
			ta=f[i-1]+a[i]+a[1];
			tb=f[i-2]+a[1]+a[2]+a[i]+a[2];
			f[i]=min(ta,tb);
		}
		printf("%d\n",f[n]);
	}
	return 0;
}



【POJ1700】Crossing River 贪心,附贪心问题的一系列详细解析