Codeforces-1475D Cleaning the Phone


Problem

Portal


Thoughts

显然对于相同cp的app,我们优先选择更大的体积的app最优。


Accepted Code

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N = 2e5+10;

int v[N], a1[N], a2[N], pre2[N];

bool cmp(const int &a, const int &b) {return a > b;}

signed main()
{
    int T; cin >> T;
    while(T -- )
    {
        int n, m;
        cin >> n >> m;
        a1[0] = a2[0] = 0;
        for(int i = 1 ; i <= n ; i ++ ) cin >> v[i];
        for(int i = 1 ; i <= n ; i ++ ) 
        {
            int b; cin >> b;
            if(b == 1) a1[++a1[0]] = v[i];
            else a2[++a2[0]] = v[i];
        }
        sort(a1+1, a1+a1[0]+1, cmp);
        sort(a2+1, a2+a2[0]+1, cmp);
        for(int i = 1 ; i <= a2[0] ; i ++ ) pre2[i] = pre2[i-1] + a2[i];
        int ans = 0x3f3f3f3f, sum = 0;
        for(int i = 1 ; i <= a1[0] ; i ++ )
        {
            sum += a1[i];
            if(sum >= m) {ans = min(ans, i); break;}
            int k = m - sum;
            int t = lower_bound(pre2+1, pre2+a2[0]+1, k) - pre2;
            if(t == a2[0]+1) continue;
            ans = min(ans, i+2*t);
        }
        int t = lower_bound(pre2+1, pre2+a2[0]+1, m) - pre2;
        if(t != a2[0]+1) ans = min(ans, t*2);
        if(ans == 0x3f3f3f3f) puts("-1");
        else cout << ans << endl;
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Codeforces-1475F Unusual Matrix Codeforces-1475F Unusual Matrix
ProblemPortal Thoughts Accepted Code#include <bits/stdc++.h> #define int long long using namespace std; const int
Next 
Codeforces-1478D Nezzar and Board Codeforces-1478D Nezzar and Board
ProblemPortal Thoughts题意为给出一个序列xi,你可以任意挑选两个数x,y将2·x-y加入序列中,询问在是否可以在序列中发现数k。假设我们任意挑选4个数:x,y,p,q并且将2·x-y、2·p-q加入到序列中,挑选出新
  TOC