传送门
题意： 有 n 个软件，第 i 个软件占 a[i] 的内存， 但有 b[i] 的贡献；现让删除一些软件，使得释放的空间达到 m 及以上，但牺牲的贡献值又要最小，并输出牺牲的最小贡献值。
思路： 参考于大佬博客
- 根据贡献值分别为 1 和 2 将内存 a 分成 a1 和 a2两个组，肯定先删内存大的软件，再按照内存大小降序排序。
- 所以贡献值为 1 的 a1 内的软件优先被删除，再利用二分 + 前缀和的方法找到除了 a1 外 a2 内再删除多少个能使得删除内存经量大。
- 再得注意，也许只删除 a2 中最大的那个就已经满足释放内存大于等于 m ，且牺牲也相对更小，所以最后还得再比较一下。
代码实现：
#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
using namespace std;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll mod = 1e9 + 7;
const int N = 2e5 + 5;int t, n, m, a[N], b[N];
int a1[N], a2[N], pre[N], t1, t2;int cmp(int x, int y){
return x > y;
}signed main()
{
IOS;cin >> t;while(t --){
cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1; i <= n; i ++) cin >> b[i];t1 = t2 = 0;for(int i = 1; i <= n; i ++){
if(b[i]==1) a1[++t1] = a[i];else a2[++t2] = a[i];}sort(a1+1, a1+t1+1, cmp);sort(a2+1, a2+t2+1, cmp);for(int i = 1; i <= t2; i ++) pre[i] = a2[i]+pre[i-1];int ans = inf, sum = 0;for(int i = 1; i <= t1; i ++){
sum += a1[i];if(sum>=m){
ans = min(ans, i);break;}int need = m-sum;int idex = lower_bound(pre+1, pre+t2+1, need)-pre;if(idex==t2+1) continue;ans = min(ans, i+idex*2);}int idex = lower_bound(pre+1, pre+t2+1, m)-pre;if(idex!=t2+1) ans = min(ans, idex*2);cout << (ans==inf ? -1:ans) << endl;}return 0;
}