【AcWing】蓝桥杯集训每日一题Day6|多路归并|贪心|1262.鱼塘钓鱼(C++)

1262.鱼塘钓鱼

题目内容

有N个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：

即：在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼，第 2 分钟内只能钓到 8 条鱼，……，第 5 分钟以后再也钓不到鱼了。
从第 1 个鱼塘到第 2 个鱼塘需要 3 分钟，从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟，……
给出一个截止时间 T，设计一个钓鱼方案，从第 1 个鱼塘出发，希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

输入格式

共 5 行，分别表示：
第 1 行为 N；
第 2 行为第 1 分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；
第 3 行为每过 1 分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；
第 4 行为当前鱼塘到下一个相邻鱼塘需要的时间；
第 5 行为截止时间 T。

输出格式

一个整数（不超过$2^{31}-1$），表示你的方案能钓到的最多的鱼。

数据范围

1≤N≤100,
1≤T≤1000

输入样例：

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

输出样例：

76

题目解析

每个鱼塘初始最多1000条鱼
每次最少减1条鱼
每个鱼塘最多可以钓1000+999+…+1
大概是$\frac{1000^2}{2}$，50万条鱼
最多有100个鱼塘，所以最多钓5000万条鱼，不会爆int

非常经典的贪心问题，两步贪心

第一步贪心

考虑一下在最优解当中，都是从1号鱼塘出发，有没有可能来回反复走

比如在第一个鱼塘的位置钓了一分钟，第二个鱼塘钓了0分钟，第三个鱼塘钓了两分钟，第四个鱼塘钓了两分钟，又返回第三个鱼塘钓了一分钟，又路过第四个鱼塘没有钓，0分钟，又在第五个鱼塘钓了2分钟
如果出现了这样的情况
发现，我们可以把重复的路线去掉，直接从前往后走，在每个鱼塘钓的时间等于第一条路线的总时间，第一个鱼塘钓1，第二个钓0，第三个鱼塘直接钓三分钟，再去下一个鱼塘，先钓2再钓0，可以直接钓两分钟，最后一个鱼塘钓2
这样可以发现钓的总鱼数是一样的
因为每个鱼塘钓多少鱼取决于每个鱼塘钓多少次，至于先钓几分钟再钓几分钟是没有关系的
所以这两条路线钓的鱼的总数是一样的，但是第二条路线走的距离还少，花费的时间也更少
因此第二条路线比第一条路线更好一些

一定存在一个最优解，不会反复横跳，所以只需要考虑从前往后走直线的情况就可以了
可以反复横跳的话，路线数是指数级别，只走直线的话，路线数就只有n种情况

第二步，考虑时间

因为n很小，可以枚举到底是哪一条路线
从1走到m，(m就是从1到n去枚举)
比如当前枚举到4
表示走的路线是确定的，从1到4，但是在每个池塘上停留的时间是不确定的

总共消耗的时间，就是路上消耗的时间+钓鱼的时间
路线确定之后，路上消耗的时间就已经确定了，3+5+4=12，剩下的时间都可以用来钓鱼

接下来就把剩下的时间合理地分配到m个鱼塘上

分配的时候发现，每个鱼塘钓的鱼的总数取决于在这个鱼塘上停留的总时间，至于怎么分配都可以
比如第一分钟分配给第一个鱼塘，第二分钟分配给第二个鱼塘，第三分钟分配给第四个鱼塘，第四分钟分配给第二个鱼塘
分配的时候可以胡乱分配
一旦分配完之后，在这个路线上走的时候，在每个鱼塘上停留的时间等于分配给的总时间
确定了给每个鱼塘分配的总分钟数之后，走的时候，先在第一个鱼塘停留够1分钟，再去第二个鱼塘停留2分钟，再走到第三个鱼塘，以此类推

因此分配的时候是完全不用考虑顺序的

如果是随便分配的话，如何分配剩余的时间

假设还剩c分钟，如何分配这c分钟可以取得钓鱼数的最大值
在分配的时候，比如给第二个鱼塘分配了三分钟，一定是取前三个数，假设取的时候可以按照任意顺序取，(当然最优解一定是取前几个)
可以任意取的话，相当于是在这个大矩阵当中任意取c个数，使得总和最大
从大矩阵/集合当中取c个数，要求总和最大
非常经典的贪心模型
一定是取最大的c个

如何取出前最大的c个

可以发现每一个序列都是单调递减的
要把若干个单调序列合并成一个有序序列
就是经典的多路归并算法

多路归并思想

先找最大值，再找第二大值，以此类推

最大值怎么找，由于每个序列都是递减的，所以最大值一定是从每个序列的第一个里挑一个最大的
可以发现是20，挑完之后把20删掉
找第二大值时，从每个序列当前第一个数里挑一个最大的，是16，把16选出来，删掉
再去剩下的每个序列的最大值里挑一个最大的，挑出14
以此类推
按照这样的方式，就可以把最大的c个挑出来，这是一个多路归并算法

因为数据范围很小，所以取最大值的时候可以不用堆，直接枚举一遍就可以了

贪心与DP

将一个集合分为两类，如果每次可以证明出来某一类里一定有答案，只需要关注这一类就可以了，就是贪心
如果无法证明最优解在哪一类当中， 每一类都要求的话，就是DP

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

//a表示每个鱼塘第一次钓的鱼数，d表示每一分钟减少的鱼数，l表示相差两个鱼塘之间的距离，spend表示在这个鱼塘里一共花的时间
int a[N], d[N], l[N], spend[N];

//求当前鱼塘能钓多少鱼
int get (int k)
{
	//第一分钟能钓的鱼的数量，减去每一分钟减少的鱼数乘上经过的时间数
	return max(0, a[k] - d[k] * spend[k]);  //和0取一个最大值，不可能变成负数
}

//如果是当前的路线的话，一共可以钓多少条鱼
int work (int n, int T)//n表示枚举到的鱼塘的最终编号，
{
	int res = 0; //res表示当前钓的总鱼数
	//初始的时候每个鱼塘都没有花时间
	memset (spend, 0, sizeof spend); //先把spend清空

	//从前往后依次枚举每次从当前n个鱼塘当中取一个最大值
	for (int i = 0; i < T; i ++)
	{
		int t = 1;
		for (int j = 2; j <= n; j ++)
		{
			//如果发现第t个鱼塘当前钓的鱼小于第j个鱼塘当前钓的鱼
			if (get(t) < get(j))
				t = j;  //就把t更新成j
		}
		res += get(t); //答案加上当前鱼塘能够钓的鱼的数量
		//这个鱼塘钓完之后，经过的时间++
		spend[t] ++;
	}
	return res;
}

int main()
{
	int n, T;  
	scanf("%d", &n);  //先读入一下鱼塘的数量

	//依次读入每个鱼塘第一分钟能够钓的鱼的数量
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d", &a[i]);
	}
	//读入第二行每一分钟减少的鱼的数量
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d", &d[i]);
	}
	//读入相邻两个鱼塘之间的距离
	for (int i = 2; i <= n; i ++)
	{
		scanf("%d", &l[i]);
		//为了方便，直接预处理成前缀和，表示从第一个鱼塘到当前鱼塘一共需要花多少时间
		l[i] += l[i - 1];
	}

	scanf("%d", &T);
	//定义一下答案
	int res = 0;
	//枚举一下走哪条路线
	for (int i = 1; i <= n; i ++)
		//枚举一下路线的终点，每次取一个最大值
		res = max(res, work(i, T - l[i]));  //T减去在路上花费的时间
	//最后输出钓的鱼数的最大值
	printf ("%d\n", res);
	return 0;
}