市赛T2征求解法

bb3653 @ 2024-11-29 22:36:08

by wfc284 @ 2024-11-29 22:46:38

你居然也是hf的
反悔贪心（？）

by bb3653 @ 2024-11-29 23:05:53

@wfc284你也hf？可以算是按反悔贪心写的，但这道题有更高明的解法（老师说的？？）

by arrowpoint @ 2024-11-29 23:42:23

@bb3653 已AC

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+10;
int n,m,a[N];
int v[N],b[N],l[N];
int tmp1[N],tmp2[N],tmp3[N],pre1[N],pre2[N];

signed main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>v[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        for(int i=1;i<=m;i++) cin>>l[i];
        int cnt1 = 0,i1 = 0,i2 = 0,i3 = 0;
        for(int i=1;i<=n;i++){
            if(v[i]==1) ++cnt1,tmp1[++i1] = b[i];
            else{
                tmp2[++i2] = b[i],tmp3[++i3] = b[i];
            }
        }
        sort(tmp1+1,tmp1+i1+1);
        int max1 = tmp1[i1];
        for(int i=i1-1;i-1>0;i-=2) tmp2[++i2] = tmp1[i]+tmp1[i-1];
        for(int i=i1;i-1>0;i-=2) tmp3[++i3] = tmp1[i]+tmp1[i-1];
        sort(tmp2+1,tmp2+i2+1),sort(tmp3+1,tmp3+i3+1);
        for(int i=1;i<=i2;i++) pre1[i] = pre1[i-1]+tmp2[i2-i+1];
        for(int i=1;i<=i3;i++) pre2[i] = pre2[i-1]+tmp3[i3-i+1];
        for(int i=1;i<=m;i++){
            if(l[i]%2){
                if(!cnt1 || l[i]/2>i2) cout<<-1<<' ';
                else cout<<max1+pre1[l[i]/2]<<" ";
            }
            else{
                if(l[i]/2>i3) cout<<-1<<' ';
                else cout<<pre2[l[i]/2]<<' ';
            }
        }
        cout<<endl;
    }

    return 0;
}