模版题——多路归并

题目：https://www.acwing.com/problem/content/1264/

这个题目主要考的是多路归并的思想和两步贪心

1.第一步贪心，我们不会出现反复横跳的情况

2.第二部贪心，对于我们能到达的前n个鱼塘，我们在这剩余的t时间，要钓到的肯定是前t个最大的，这就涉及到了多路归并问题。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e2 + 10;
const int mod  = 998244353;
int a[N],d[N],l[N],spend[N];
int get(int k){
    return max(0,a[k] - d[k]*spend[k]); //计算当前鱼塘能钓的鱼的数量
}
int work(int n,int T){
    int res = 0;
    memset(spend,0,sizeof spend);
    for (int i = 0; i < T; ++i) {
        int t = 1;
        for (int j = 2; j <= n; ++j) {
            if(get(t) < get(j)){        //枚举n个鱼塘当前能钓的最大数量
                t = j;
            }
        }
        res += get(t);  //加上当前能钓的最大的鱼的数量
        spend[t]++; //该鱼塘时间+1
    }
    return res;
}

void solve(){
    int n,T;
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin>>d[i];
    }
    for (int i = 2; i <= n; ++i) {
        cin>>l[i];
        l[i] += l[i-1];
    }
    cin>>T;
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res = max(res,work(i,T-l[i]));  //第一步贪心，不会反复横跳，所以可以枚举最大能到达的鱼塘位置
    }
    cout<<res<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0 ;
}