【題解】Codeforces 1475D. Cleaning the Phone

【題目敘述】https://codeforces.com/contest/1475/problem/D
【解題想法】貪心,二分搜

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m, a[200005], b[200005];
long long tot;
vector <long long> vx, vy;
 
bool cmp(int x, int y){
    return x > y;
}
inline int find(int x){
    if (x <= 0) return 0;
    return ((lower_bound(vy.begin(), vy.end(), x)-vy.begin())+1)*2;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--){
        cin >> n >> m;
        tot = 0;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            tot += a[i];
        }
        vx.clear();
        vy.clear();
        for (int i = 1; i <= n; i++){
            cin >> b[i];
            if (b[i] == 1) vx.push_back(a[i]);
            else vy.push_back(a[i]);
        }
        if (tot < m){
            cout << -1 << "\n";
            continue;
        }
        sort(vx.begin(), vx.end(), cmp);
        sort(vy.begin(), vy.end(), cmp);
        for (int i = 1; i < (int)vx.size(); i++){
            vx[i] += vx[i-1];
        }
        for (int i = 1; i < (int)vy.size(); i++){
            vy[i] += vy[i-1];
        } 
        int ans = 1e9;
        if (vy.empty()){
            cout << (int)(lower_bound(vx.begin(), vx.end(), m)-vx.begin())+1 << "\n";
            continue;
        }
        if (m <= vy.back()){
            ans = min(ans, find(m));
        }
        for (int i = 0; i < (int)vx.size(); i++){
            if (m-vx[i] <= vy.back()) ans = min(ans, (i+1)+find(m-vx[i]));
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends