平均數

貪心 - APCSC
https://atcoder.jp/contests/abc236/tasks/abc236_e

平均最大化¶

$N$ 個物品重量與價值分別為 $w_{i}$ , $v_{i}$ ，選 $K$ 個，求單位重量的價值最大多少

思路

\begin{aligned} \frac{\sum v_{i}}{\sum w_{i}} \geq x \\ \Rightarrow & \sum v_{i} \geq \sum (x \times w_{i}) \\ \Rightarrow & \sum (v_{i} - x \times w_{i}) \geq 0 \end{aligned}

二分搜 $x$ ，選 $(v_{i} - x \times w_{i})$ 最大的 $K$ 個判斷

code

bool check (double x) {
    for (int i = 0; i < n; i++) {
        c[i] = w[i]- x * v[i];
    }
    sort(c, c + n,greater<double>());

    float sum = 0;
    for (int i = 0; i < k; i++) {
        sum += c[i];
    }

    return sum >= 0;
}

while (R - L > 0.0001) {
    double m = (L + R) / 2;
    if (check (m)) {
        L = m;
    } else {
        R = m;
    }
}

區間平均¶

區間平均

給定 $a_{1}, . . ., a_{n}$ 問可否選出 $a_{l}, . . ., a_{r}$ 使得平均為 $x$

思路

將 $a_{i}$ 的變成 $a_{i} - x$

問題就變成取 $p r e_{i} - p r e_{j} = 0$

最大平均區間¶

CF EDU A. Maximum Average Segment

給定 $a_{1}, . . ., a_{n}$ 問可否選出長度 $\geq k$ 的 subarray 使得平均最大，輸出這個 subarray 的左右界

$k \leq n \leq 10^{5}, 0 \leq a_{i} \leq 100$

思路

二分搜平均值 $x$

$check (x)$ 是檢查有沒有平均大於等於 $x$ 的

也就是看 $p r e (i) - p r e (j) \geq 0$

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

int n, k;
int ansl, ansr;
int a[maxn];
double b[maxn];

bool check(double x) {
    for (int i = 1; i <= n; i++) {
        b[i] = (double)b[i - 1] + a[i] - x;
    }
    double mn = 0;
    int idx = 1;
    for (int i = k; i <= n; i++) {
        if (b[i - k] < mn) { // 技巧
            mn = b[i - k];
            idx = i - k + 1;
        }
        if (b[i] - mn >= 0) {
            ansl = idx, ansr = i;
            return true;
        }
    }
    return false;
}

signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    double l = 0, r = 105;
    for (int i = 0; i < 100; i++) {
        double mid = (double)(l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    check(l);
    cout << ansl << ' ' << ansr << '\n';
} 

最短平均路¶

最短平均路 CF EDU B. Minimum Average Path

給定一個 $n$ 點 $m$ 邊的 DAG，邊帶權，問從 $1 \to n$ 的 path 上權重的平均最小可以是多少

$n \leq 10^{5}, m \leq 10^{5}$

思路

跟上面最大平均區間一樣，我們去二分搜平均值 $x$ ，將邊權都 $- x$ ，看有沒有一條 path 的總和 $\leq 0$ 。我們可以令 $d p [i] =$ 走到點 $i$ 的最小權值是多少， $d p [v] = min {d p [u] + w}$

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const double INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

int n, m;
double dp[maxn];
int par[maxn];
vector<pii> G[maxn];

bool check(double x) {
    fill(dp, dp + n + 1, INF);
    fill(par, par + n + 1, -1);
    dp[1] = 0;
    for (int i = 1; i <= n; i++) {
        for (auto [v, w] : G[i]) {
            double val = (double)dp[i] + w - x;
            if (dp[v] > val) {
                dp[v] = val;
                par[v] = i;
            }
        }
    }
    return dp[n] <= 0;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].pb({v, w});
    }

    double l = 0, r = 105;
    for (int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    check(l);

    stack<int> stk;
    int x = n;
    stk.push(x);
    while (par[x] != -1) {
        x = par[x];
        stk.push(x);
    }
    cout << stk.size() - 1 << '\n';
    while (stk.size()) {
        cout << stk.top() << ' ';
        stk.pop();
    }
}