01分数规划

二分答案，当前答案为 $mid$ 时，把第 $i$ 个物品的权值设为 $a_i - mid \times b_i$，然后取最大的 $k$ 个即可得到最大值。

二分答案，当前答案为 $mid$ 时，我们遍历一下区间的右端点 $r$，从 $1$ 遍历到 $n$，固定一个 $r$，则我们需要找到 左端点 $l$ 使得 $\frac{\sum\limits_{i=l}^ra_i}{r-l+1}$ 最大。

令 $\frac{\sum\limits_{i=l}^ra_i}{r-l+1} \geq mid$，有 $\sum\limits_{i=l}^r(a_i - mid) \geq 0$，

定义一个新的数组$b$，其中 $b_i = a_i - mid$。

左边的最大值就是 $b$ 这个数组中最大的连续区间，用前缀和即可。

另外一种思考方法:

二分答案，当前答案为 $mid$ 时，我们遍历一下区间的右端点 $r$，从 $1$ 遍历到 $n$，固定一个 $r$，则我们需要找到 左端点 $l$ 使得 $\frac{sum[r] - sum[l-1]}{r-l+1}$ 最大。

$\frac{sum[r] - sum[l-1]}{r-l+1} \geq mid$ ，有 $(mid \times (l-1) - sum[l-1]) - (mid \times r - sum[r]) \geq 0$

因为 $r$ 固定，所以只要找 $mid*l - sum[l]$ 的最大值，其中 $l \in [\max(0, r-T), r-s]$。

遍历 $r$ 的时候，维护一个单调队列即可。

#include <bits/stdc++.h>

using namespace std;
const double eps = (double)1e-6;
const int maxn = 1e5+5;

int n, s, t;
int arr[maxn];
int sum[maxn];
double a[maxn];

int q[maxn];
int head = 0, tail = -1;

double ans = -1e4;

bool check(double cur) {
    for (int i = 0; i <= n; i++) a[i] = cur * (double)(i) - (double)(sum[i]);
    double res = -1e18;
    head = 0, tail = -1;

    for (int r = s; r <= n; r++) {
        while (head <= tail && q[head] < r-t) head++;
        while (head <= tail && a[q[tail]] < a[r-s]) tail--;
        q[++tail] = r-s;

        res = max(res, a[q[head]] - a[r]);
    }

    // for (int r = 1; r <= n; r++) {
    //     double tmp = -1e18;
    //     for (int i = max(0, r-t); i <= r-s; i++) {
    //         tmp = max(tmp, a[i]);
    //     }
    //     res = max(res, tmp - a[r]);
    // }
    if (res >= 0) return 1;
    return 0;
}


int main() {

    scanf("%d%d%d",&n,&s,&t);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        sum[i] = sum[i-1] + arr[i];
    }
    
    double l = -1e4, r = 1e4;
    while (abs(l-r) > eps) {
        double mid = (l+r) * 0.5;
        if (check(mid)) {
            l = mid;
            ans = mid;
        } else {
            r = mid;
        }
    }

    printf("%.3f\n", ans);
}

和例1几乎一样，但是多了一个 $\sum b_i \geq W$ 的限制。

设 $d_i = a_i - mid \times b_i$，然后我们要做的事就是：

选取一组$i$，保证在 $\sum b_i \geq W$ 的前提下，使得 $\sum d_i$ 最大

可以用01背包解决，令 $dp[n][k]$ 为：使用前 $n$ 个元素，$\sum b_i = k$ 时， $\sum d_i$ 的最大值。

那么答案就是 $dp[n][W]$。

如果在状态转移过程中出现 $k > W$，直接转移到 $k = W$ 的状态上即可。

注: 写01背包的时候不要忘了 倒序枚举 ！

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

const double eps = (double)1e-6;
const int maxn = 255;

int n,W;
int w[maxn], t[maxn];

double dp[1001];

struct node {
    double d;
    int w;
} arr[maxn];

bool check(double cur) {
    for (int i = 1; i <= n; i++) {
        arr[i] = {(double)t[i] - cur * (double)w[i], w[i]};
    }

    fill(dp, dp+1001, -1e9);
    dp[0] = 0.0;

    for (int i = 1; i <= n; i++) {
        for (int d = 1000; d >= 0; d--) {
            int tar = min(d + arr[i].w, 1000);
            dp[tar] = max(dp[tar], dp[d] + arr[i].d);
        }
    }

    for (int d = W; d <= 1000; d++) {
        if (dp[d] >= 0.0) return 1;
    }
    return 0;
}

int main() {
    scanf("%d%d", &n,&W);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &t[i]);
    }

    double l = 0.0, r = 1e6, ans = 0.0;
    while (abs(l-r) >= eps) {
        double mid = (l+r) * 0.5;
        if (check(mid)) {
            l = mid;
            ans = max(ans, mid);
        } else {
            r = mid;
        }
    }
    
    printf("%d\n", (int)((ans+5e-5) * 1000));
}

首先看条件1：$\frac{\sum\limits_i P_i}{\sum\limits_i S_i}$ 最大，仍然是分数规划的套路，二分答案。令 $d_i = P_i - mid \times S_i$

所以问题转化为求一组节点使得 $\sum d_i$ 最大。

然后就会发现，这是一个经典的树形dp模型，和 选课(洛谷P2014) 几乎一样。

具体做法和注意事项见下一篇博客。