题意简述
你有一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。你还得到了一个长度为 $n$ 的二进制数组 $b$。
你最多可以进行 $k$ 次以下操作：
选择一个索引 $i$ ($1 \leq i \leq n$)，使得 $b_i = 1$。然后将 $a_i$ 增加 1（即将 $a_i$ 增加 1）。
你的得分定义为 $\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$，其中 $c_i$ 表示通过从 $a$ 中删除 $a_i$ 获得的长度为 $n-1$ 的数组。换句话说，你的得分是所有 $1$ 到 $n$ 的 $i$ 中，$a_i + \operatorname{median}(c_i)$ 的最大值。
找出如果你最佳地执行这些操作，能达到的最大得分。
对于任意数组 $p$，$\operatorname{median}(p)$ 定义为数组中第 $\left\lfloor \frac{|p|+1}{2} \right\rfloor$ 小的元素。例如，$\operatorname{median} \left( [3,2,1,3] \right) = 2$ 和 $\operatorname{median} \left( [6,2,4,5,1] \right) = 4$。
思路分析
考虑如果不进行操作，我的得分应该为多少？
将数组按升序排序。
显然得分应该为数组最大值 $a_n$ 加上去掉 $a_n$ 后的中位数 $a_m$。
接着再考虑进行至多 $k$ 次操作后的结果。
如果 $a_n$ 是可更改的，那么每对 $a_n$ 进行一次操作都会直接使得分增加 $1$。
那么在这种情况下，对 $a_n$ 进行 $k$ 次操作一定是最优的，此时得分为 $a_n + a_m + k$。
那么如果 $a_n$ 不可更改呢？
此时我们有两条路可走。
第一条路是改最大值，即找到最大的可被修改的 $a_t$，对其进行 $k$ 次操作。
如此会浪费掉一些操作次数用来将 $a_t$ 填到 $a_n$。
第二条路是修改中位数。
修改中位数嘛，如果通过排序不太好动态去求。
我们可以二分一个中位数然后去看有几个数比它大。
如果加上 $k$ 次操作的话，我们可以从大到小寻找小于这个中位数的可修改的 $a_i$，将其修改为这个中位数。
$k$ 次操作过后，
如果有不少于 $\lfloor\dfrac{n+1}{2}\rfloor$ 个数比它大，说明这个中位数选小了，左边界右移。
否则说明中位数选大了，右边界左移。
两条路的得分取最大值即可。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include<bits/stdc++.h>
using namespace std;
const int maxN = 3e5 + 10;
struct Dt{
int a,b,_id;
friend bool operator < (Dt A, Dt B){
return A.a < B.a;
}
}A[maxN];
int B[maxN];
int N,K;
bool check(int mid){
stack<int> s;
while(!s.empty()) s.pop();
int cnt = 0;
for(int i = 1;i<=N;i++){
if(A[i].a >= mid) cnt++;
else if(A[i].b){
s.push(mid-A[i].a);
}
}
int kk = K;
while(!s.empty()){
int x = s.top();
s.pop();
if(kk >= x){
kk -= x;
cnt++;
}
}
return (cnt > ((N + 1) >> 1));
}
inline void solve(){
scanf("%d%d",&N,&K);
for(int i = 1;i<=N;i++) scanf("%d",&A[i].a);
for(int i = 1;i<=N;i++) scanf("%d",&A[i].b);
for(int i = 1;i<=N;i++) A[i]._id = i;
sort(A+1,A+1+N);
int t = (N) >> 1;
long long ans = 0;
if(A[N].b){
ans += A[N].a;
ans += K;
ans += A[t].a;
printf("%lld\n",ans);
return;
}else{
int l = 1;
int r = 1e9;
int aans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)){
l = mid + 1;
aans = mid;
}else{
r = mid - 1;
}
}
ans = aans + A[N].a;
for(int i = N;i>=1;i--){
if(A[i].b){
A[i].a += K;
break;
}
}
sort(A+1,A+1+N);
ans = max(ans,A[N].a+A[(N)>>1].a*1ll);
printf("%lld\n",ans);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
|