CodeForces 1201C Maximum Median [二分答案]

发布于 2019-08-07  611 次阅读


题目大意是给定一个长度为奇数的数列,每次操作可以将数列中某个数加一,在k次操作之后问该序列能取到的最大中位数是多少。

原本想了个利用二分查找进行模拟的办法,复杂度是\( O(k \cdot n \cdot logn) \),结果TLE。后来想到可以二分答案。对于给定的k,k次操作以内使得数列中较大的那一半的数达到p,则答案至少为p。二分答案,复杂度为\( O(n \cdot logk) \)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>



#ifdef _MSC_VER
#define scanf scanf_s
#endif // _MSC_VER

#ifndef ONLINE_JUDGE
#define debug(x) std::cout<<x<<std::endl;
#else
#define debug(x) ;
#endif;

using namespace std;

bool check(const vector<long long>& v, long long k, long long possible_median) {
	for (long long i = v.size() / 2; i < v.size() && v[i] < possible_median && k >= 0; ++i) {
		k -= possible_median - v[i];
	}
	return k >= 0;
}

int main() {
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	long long n, k;
	cin >> n >> k;
	if (n == 1) {
		long long ans;
		cin >> ans;
		ans += k;
		cout << ans << endl;
		return 0;
	}
	vector<long long> arr(n);
	for (long long i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());
	long long low = 1, high = static_cast<long long>(1e18 + 5);
	long long mid;
	bool flag;
	while (low <= high) {
		mid = (low + high) >> 1;
		flag = check(arr, k, mid);
		if (flag) low = mid + 1;
		else high = mid - 1;
	}
	long long ans = flag ? mid : mid-1;
	cout << ans << endl;
	return 0;
}

终有一日, 仰望星空