题解归档 - cf104118H

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118H
• 本地来源：problems/cf104118H/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/H
• 原始标题：Gym 104118H - HIIT

思路

Gym 104118H - HIIT

Objectives are lexicographic:

1. maximize number of non-skipped exercises;
2. among those, maximize intense exercises.

First objective:

• The cheapest way to do m exercises is the sum of the m smallest a_i, so greedily find the maximum feasible m.

Second objective:

• Fix m and ask if exactly r intense exercises are possible.
• Let d_i = b_i - a_i.
• In an optimal solution with r intense and m-r easy, no intense exercise can have larger d than an easy exercise: swapping their modes would reduce cost.

• Therefore, after sorting by d, there is a cut:

  • choose the r smallest b_i from the prefix as intense;
  • choose the m-r smallest a_i from the suffix as easy.
• For a fixed r, scan all cuts with two heaps to get the minimum cost.
• Binary search the largest feasible r, then reconstruct from its best cut.

Complexity: O(n log n log n), memory O(n).

Checks:

• sample 1
• statement samples 2-4 reconstructed from PDF
• randomized brute force for n <= 7

代码

来源：problems/cf104118H/solution.cpp

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

const ll INF = (1LL << 62);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll x;
    cin >> n >> x;
    vector<ll> a(n), b(n);
    for (ll &v : a) cin >> v;
    for (ll &v : b) cin >> v;

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        ll di = b[i] - a[i], dj = b[j] - a[j];
        if (di != dj) return di < dj;
        return i < j;
    });

    vector<ll> only_a = a;
    sort(only_a.begin(), only_a.end());
    int done = 0;
    ll sum = 0;
    while (done < n && sum + only_a[done] <= x) {
        sum += only_a[done];
        ++done;
    }

    vector<ll> left(n + 1), right(n + 2);

    auto calc = [&](int intense) -> pair<ll, int> {
        fill(left.begin(), left.end(), INF);
        fill(right.begin(), right.end(), INF);

        if (intense == 0) {
            fill(left.begin(), left.end(), 0);
        } else {
            priority_queue<ll> pq;
            ll cur = 0;
            for (int p = 1; p <= n; ++p) {
                int id = ord[p - 1];
                pq.push(b[id]);
                cur += b[id];
                if ((int)pq.size() > intense) {
                    cur -= pq.top();
                    pq.pop();
                }
                if ((int)pq.size() == intense) left[p] = cur;
            }
        }

        int easy = done - intense;
        if (easy == 0) {
            fill(right.begin(), right.end(), 0);
        } else {
            priority_queue<ll> pq;
            ll cur = 0;
            for (int p = n; p >= 1; --p) {
                int id = ord[p - 1];
                pq.push(a[id]);
                cur += a[id];
                if ((int)pq.size() > easy) {
                    cur -= pq.top();
                    pq.pop();
                }
                if ((int)pq.size() == easy) right[p] = cur;
            }
        }

        ll best = INF;
        int cut = 0;
        for (int p = 0; p <= n; ++p) {
            if (left[p] == INF || right[p + 1] == INF) continue;
            ll val = left[p] + right[p + 1];
            if (val < best) {
                best = val;
                cut = p;
            }
        }
        return {best, cut};
    };

    int lo = 0, hi = done;
    while (lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        if (calc(mid).first <= x) lo = mid;
        else hi = mid - 1;
    }

    int intense = lo;
    auto [best_cost, cut] = calc(intense);
    (void)best_cost;

    string ans(n, '0');
    vector<int> pref(ord.begin(), ord.begin() + cut);
    if (intense > 0 && intense < (int)pref.size()) {
        nth_element(pref.begin(), pref.begin() + intense, pref.end(), [&](int i, int j) {
            if (b[i] != b[j]) return b[i] < b[j];
            return i < j;
        });
    }
    for (int t = 0; t < intense; ++t) ans[pref[t]] = '2';

    int easy = done - intense;
    vector<int> suff(ord.begin() + cut, ord.end());
    if (easy > 0 && easy < (int)suff.size()) {
        nth_element(suff.begin(), suff.begin() + easy, suff.end(), [&](int i, int j) {
            if (a[i] != a[j]) return a[i] < a[j];
            return i < j;
        });
    }
    for (int t = 0; t < easy; ++t) ans[suff[t]] = '1';

    cout << ans << '\n';
    return 0;
}