鱼塘钓鱼-贪心

题目来源：Acwing 1262. 鱼塘钓鱼&洛谷 P1717 钓鱼&NEFU OJ-364 鱼塘钓鱼
（题目描述来自Acwing，代码为其AC代码，后附三者代码区别）

题目描述

有 N 个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：N=5 时，如下表：
鱼塘编号 1 2 3 4 5
第1分钟能钓到的鱼的数量（1…1000） 10 14 20 16 9
每钓鱼1分钟钓鱼数的减少量（1…100) 2 4 6 5 3
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟） 3 5 4 4
即：在第 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³¹−1），表示你的方案能钓到的最多的鱼。

数据范围

1≤N≤100,
1≤T≤1000

输入样例

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

输出样例

76

OP

看到这道题第一反应是DP，即 dp[ i ][ j ] 为有前 i 个池子时，时间 j 内能钓出的最大数量，但是最终没有解决有效性问题/大概。
最后决定贪心。

思路

由于是从第一个鱼塘开始，则若确定所到的最后一个鱼塘，便可知钓鱼的总时间（总时间-移动用时），接下来求出钓鱼量即可。

求出钓鱼量即要明确在各个鱼塘中分别的钓鱼量。为了保证总量最大，我们可以做如下处理：
对钓满前 a 个鱼塘来说
把各个鱼塘的初始分钟鱼量加入一降序的优先队列中，优先钓出最大的分钟鱼量；
如果第 i 个池子的第 j 分钟鱼量被钓出，则此池子的第 j + 1 分钟鱼量入队；
持续进行 钓鱼时间 次。

在这个过程中，虽然每分钟钓出的鱼来自鱼塘的顺序不是1,2,…但是全部都来自前 a 个鱼塘。如果每次钓出的鱼共有n1次来自1鱼塘，n2次来自2鱼塘，… ，na次来自a鱼塘，我们便可以认为在1鱼塘钓 n1 分钟鱼后，转移至2鱼塘，在2鱼塘钓 n2 分钟，…，在a鱼塘钓 na 分钟。实际上是是等价的。

知道了钓满前 a 个鱼塘的钓鱼最大量，我们便可以遍历a 1~n，找最大值。

时间复杂度O( T + N )

代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n
        ,fo[102]={0},del[102]={0},tonext[102]={0},t
        ,i,j,k,fmx=0;
    cin>>n;//总鱼塘数
    for(i=1;i<=n;i++)scanf("%d",&fo[i]);//初始分钟鱼量
    for(i=1;i<=n;i++)scanf("%d",&del[i]);//每分钟衰减量
    for(i=1;i<=n-1;i++)scanf("%d",&tonext[i]);//到下一鱼塘用时
    cin>>t;//总时间
    for(i=1;i<=n;i++)//遍历最后一个鱼塘的编号
    {
        int ti=t,fiall=0;//fiall是前 i 个鱼塘中的最大钓鱼量
        priority_queue<pair<int,int> >que;//优先队列，除了存储分钟鱼量还需存储对应的鱼塘编号，便于计算下一分钟到鱼量
        pair<int,int>fz;
        for(j=1;j<i;j++)ti-=tonext[j];//计算钓满前 i 个鱼塘的剩余钓鱼时间（减去转移用时）
        for(j=1;j<=i;j++)que.push(make_pair(fo[j],j));//入队初始分钟鱼量
        while(ti>0)//这里没有用while(ti--)是不排除ti已经小于0的情况
        {
            ti--;
            fz=que.top();//最大量出队
            que.pop();
            fiall+=fz.first;
            que.push(make_pair((fz.first-del[fz.second])>=0?(fz.first-del[fz.second]):0,fz.second));
            //入队该池鱼的下一分钟鱼量，避免负数
        }
        if(fiall>fmx){fmx=fiall;}
    }
    printf("%d",fmx);
    return 0;
}

注1：对于priority_queue<pair<int,int> >，默认排序依据是 pair.first 的降序；
注2：对于洛谷，调整接收顺序后，时间*12 即可；
注3：NEFU oj 上是多组输入。

ED

有点类似于序列合并，具体思想是相似的。