灵茶之二分01
链接
题目大意
输入 n(1≤n≤500) x(1≤x≤\(10^5\)) 和长为 n 的数组 a(1≤a[i]≤\(10^5\))。 向 a 中添加尽量少的数,使得 a 的中位数恰好等于 x。 输出添加的元素个数。 注:如果 n 是偶数,中位数取正中间左边那个。例如 a=[1,3,5,7] 的中位数是 3。
进阶:你能做到(预处理后)对于任意 x,都只用 O(log n) 的时间回答吗?
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, x, t;
int a[N];
void solve() {
cin >> n >> x;
int left,right,final_length;
for(int i = 1;i <= n;++i) cin >> a[i];
sort(a + 1,a + n + 1);
// 寻找小于x的数有多少?
left = lower_bound(a + 1,a + 1 + n,x) - (a + 1);
// 寻找大于x的数有多少?
right = n - (upper_bound(a + 1,a + 1 + n,x) - (a + 1));
// 求添加完后最大长度
final_length = max({n,left * 2 + 1,right * 2}); // {left} x {left} {right} {right}
cout << final_length - n << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
t = 1;
for (int _ = 0; _ < t; _++)
solve();
return 0;
}
标签:二分,right,int,灵茶,中位数,01,left
From: https://www.cnblogs.com/gebeng/p/18097333