题解：CF1475D Cleaning the Phone

skimlight · 2026-08-10 22:18:18 · 题解

题意

有 n 个应用，每个应用有内存 a_i 和便利值 b_i（取值 1 或 2）。要删除若干应用使释放的内存至少为 m，求删除应用的便利值之和的最小值。

思路

按重要度将应用分为两组（b=1 和 b=2），分别从大到小排序并求前缀和。枚举选择多少个 b=1 的应用（记为 i），那么还需要从 b=2 的应用中选至少 m-s1_i 的内存（s1_i 表示 b=1 时数组元素的前缀和），即在 b=2 的前缀和数组 s2 中二分查找所需数量，答案取最小值。若所有应用总内存 <m，则无解。

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

const int N = 2e5 + 5;
const ll inf = 1e18;

int n, m;
ll a[N], b[N];
ll a1[N], a2[N], s1[N], s2[N];

void Clear() {
    for (int i = 1; i <= n; ++i) {
        a1[i] = a2[i] = s1[i] = s2[i] = 0;
    }
}

void Solve() {
    cin >> n >> m;
    Clear();
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    int len1 = 0, len2 = 0;
    for (int i = 1; i <= n; ++ i) {
        cin >> b[i];
        if (b[i] == 1) {
            a1[++ len1] = a[i];
        }
        else {
            a2[++ len2] = a[i];
        }
    }
    sort(a1 + 1, a1 + len1 + 1, greater<ll>());
    sort(a2 + 1, a2 + len2 + 1, greater<ll>());
    for (int i = 1; i <= len1; ++ i) {
        s1[i] = s1[i - 1] + a1[i];
    }
    for (int i = 1; i <= len2; ++ i) {
        s2[i] = s2[i - 1] + a2[i];
    }
    ll ans = inf;
    for (int i = 0; i <= len1; ++ i) {
        ll now = s1[i];
        if (now >= m) {
            ans = min(ans, 1LL * i);
            continue;
        }
        ll need = m - now;
        int p = lower_bound(s2 + 1, s2 + len2 + 1, need) - s2;
        if (p <= len2) {
            ans = min(ans, 1LL * i + 2LL * p);
        }
    }
    cout << (ans == inf ? -1 : ans) << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) Solve();
    return 0;
}