【題目敘述】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";
}
}