JZTXT

多路归并

发布时间 2023-04-01 17:22:37作者: lyc2002

[acwing]1262. 鱼塘钓鱼

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n;
int a[N], d[N], t[N]; // t[i] 表示从第 1 个池塘走到第 i 个池塘所需时间
int T;
int spend[N]; // spend[i] 表示在第 i 个池塘钓了多长时间
int res;

// 当前能钓得的鱼数
int get(int i)
{
    return max(0, a[i] - d[i] * spend[i]);
}

int solve(int n, int t)
{
    if (t <= 0) return 0;
    
    memset(spend, 0, sizeof(spend));
    
    int res = 0;
    priority_queue<PII> h;
    for (int i = 1; i <= n; i++) h.push({get(i), i});
    while (t-- > 0) {
        auto tmp = h.top();
        if (tmp.first == 0) break;
        h.pop();
        res += tmp.first;
        spend[tmp.second]++;
        h.push({get(tmp.second), tmp.second});
    }
    
    return res;
}

int main()
{
    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", &t[i]);
        t[i] += t[i - 1];
    }
    scanf("%d", &T);
    
    for (int i = 1; i <= n; i++) 
        res = max(res, solve(i, T - t[i]));
    
    printf("%d", res);
    
    return 0;
}